子数组中占绝大多数的元素

1157. 子数组中占绝大多数的元素

设计一个数据结构，有效地找到给定子数组的 多数元素 。

子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。

实现 MajorityChecker 类:

MajorityChecker(int[] arr) 会用给定的数组 arr 对 MajorityChecker 初始化。
int query(int left, int right, int threshold) 返回子数组中的元素 arr[left...right] 至少出现 threshold 次数，如果不存在这样的元素则返回 -1。

示例 1：

输入:
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
输出：
[null, 1, -1, 2]

解释：
MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // 返回 1
majorityChecker.query(0,3,3); // 返回 -1
majorityChecker.query(2,3,2); // 返回 2

提示：

1 <= arr.length <= 2 * 10⁴
1 <= arr[i] <= 2 * 10⁴
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
调用 query 的次数最多为 10⁴

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class MajorityChecker { public: MajorityChecker(vector<int>& arr) { } int query(int left, int right, int threshold) { } }; /** * Your MajorityChecker object will be instantiated and called as such: * MajorityChecker* obj = new MajorityChecker(arr); * int param_1 = obj->query(left,right,threshold); */

javascript 解法, 执行用时: 296 ms, 内存消耗: 63.9 MB, 提交时间: 2023-04-16 11:12:42

/**
 * @param {number[]} arr
 */
const K = 20;
var MajorityChecker = function(arr) {
    this.arr = arr;
    this.loc = new Map();
    for (let i = 0; i < arr.length; ++i) {
        if (!this.loc.has(arr[i])) {
            this.loc.set(arr[i], []);
        }
        this.loc.get(arr[i]).push(i);
    }
};

/** 
 * @param {number} left 
 * @param {number} right 
 * @param {number} threshold
 * @return {number}
 */
MajorityChecker.prototype.query = function(left, right, threshold) {
    const length = right - left + 1;
    for (let i = 0; i < K; ++i) {
        const x = this.arr[left + Math.floor(Math.random() * length)];
        const pos = this.loc.get(x);
        const occ = searchEnd(pos, right) - searchStart(pos, left);
        if (occ >= threshold) {
            return x;
        } else if (occ * 2 >= length) {
            return -1;
        }
    }

    return -1;
};

const searchStart = (pos, target) => {
    let low = 0, high = pos.length;
    while (low < high) {
        const mid = low + Math.floor((high - low) / 2);
        if (pos[mid] >= target) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

const searchEnd = (pos, target) => {
    let low = 0, high = pos.length;
    while (low < high) {
        const mid = low + Math.floor((high - low) / 2);
        if (pos[mid] > target) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * var obj = new MajorityChecker(arr)
 * var param_1 = obj.query(left,right,threshold)
 */

golang 解法, 执行用时: 268 ms, 内存消耗: 12.2 MB, 提交时间: 2023-04-16 11:11:32

type MajorityChecker struct {
    arr []int
    loc map[int][]int
}

func Constructor(arr []int) MajorityChecker {
    rand.Seed(time.Now().UnixNano())
    loc := map[int][]int{}
    for i, x := range arr {
        loc[x] = append(loc[x], i)
    }
    return MajorityChecker{arr, loc}
}

func (mc *MajorityChecker) Query(left, right, threshold int) int {
    length := right - left + 1
    for i := 0; i < 20; i++ {
        x := mc.arr[rand.Intn(right-left+1)+left]
        pos := mc.loc[x]
        occ := sort.SearchInts(pos, right+1) - sort.SearchInts(pos, left)
        if occ >= threshold {
            return x
        }
        if occ*2 >= length {
            break
        }
    }
    return -1
}


/**
 * Your MajorityChecker object will be instantiated and called as such:
 * obj := Constructor(arr);
 * param_1 := obj.Query(left,right,threshold);
 */

python3 解法, 执行用时: 544 ms, 内存消耗: 26.4 MB, 提交时间: 2023-04-16 11:11:08

class MajorityChecker:
    k = 20

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.loc = defaultdict(list)

        for i, val in enumerate(arr):
            self.loc[val].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        arr_ = self.arr
        loc_ = self.loc
        
        length = right - left + 1
        for i in range(MajorityChecker.k):
            x = arr_[randint(left, right)]
            pos = loc_[x]
            occ = bisect_right(pos, right) - bisect_left(pos, left)
            if occ >= threshold:
                return x
            elif occ * 2 >= length:
                return -1

        return -1

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)

python3 解法, 执行用时: 1456 ms, 内存消耗: 50.6 MB, 提交时间: 2023-04-16 11:10:47

class Node:
    def __init__(self, x: int = 0, cnt: int = 0):
        self.x = x
        self.cnt = cnt
    
    def __iadd__(self, that: "Node") -> "Node":
        if self.x == that.x:
            self.cnt += that.cnt
        elif self.cnt >= that.cnt:
            self.cnt -= that.cnt
        else:
            self.x = that.x
            self.cnt = that.cnt - self.cnt
        return self

class MajorityChecker:
    def __init__(self, arr: List[int]):
        self.n = len(arr)
        self.arr = arr
        self.loc = defaultdict(list)

        for i, val in enumerate(arr):
            self.loc[val].append(i)
        
        self.tree = [Node() for _ in range(self.n * 4)]
        self.seg_build(0, 0, self.n - 1)

    def query(self, left: int, right: int, threshold: int) -> int:
        loc_ = self.loc

        ans = Node()
        self.seg_query(0, 0, self.n - 1, left, right, ans)
        pos = loc_[ans.x]
        occ = bisect_right(pos, right) - bisect_left(pos, left)
        return ans.x if occ >= threshold else -1
    
    def seg_build(self, idx: int, l: int, r: int):
        arr_ = self.arr
        tree_ = self.tree

        if l == r:
            tree_[idx] = Node(arr_[l], 1)
            return
        
        mid = (l + r) // 2
        self.seg_build(idx * 2 + 1, l, mid)
        self.seg_build(idx * 2 + 2, mid + 1, r)
        tree_[idx] += tree_[idx * 2 + 1]
        tree_[idx] += tree_[idx * 2 + 2]

    def seg_query(self, idx: int, l: int, r: int, ql: int, qr: int, ans: Node):
        tree_ = self.tree

        if l > qr or r < ql:
            return
        
        if ql <= l and r <= qr:
            ans += tree_[idx]
            return

        mid = (l + r) // 2
        self.seg_query(idx * 2 + 1, l, mid, ql, qr, ans)
        self.seg_query(idx * 2 + 2, mid + 1, r, ql, qr, ans)

# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)

上一题

下一题

详情