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

[MyLinChi]

问题

实现一个 MajorityChecker 的类，它应该具有下述几个 API：

MajorityChecker(int[] arr) 会用给定的数组 arr 来构造一个 MajorityChecker 的实例。
int query(int left, int right, int threshold) 有这么几个参数：
0 <= left <= right < arr.length 表示数组 arr 的子数组的长度。
2 * threshold > right - left + 1，也就是说阈值 threshold 始终比子序列长度的一半还要大。
每次查询 query(...) 会返回在 arr[left], arr[left+1], ..., arr[right] 中至少出现阈值次数 threshold 的元素，如果不存在这样的元素，就返回 -1。

 

示例：

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 <= 20000
1 <= arr[i] <= 20000
对于每次查询，0 <= left <= right < len(arr)
对于每次查询，2 * threshold > right - left + 1
查询次数最多为 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/online-majority-element-in-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

求解

法一：
暴力法，先求众数，再算出众数的次数，然后返回。时间复杂度O(n)

package com.leetcode;

//1157
public class MajorityChecker {
    private int[] num;

    public MajorityChecker(int[] arr) {
        num = new int[arr.length];
        for(int i=0;i<arr.length;num[i]=arr[i],++i);
    }

    public int query(int left, int right, int threshold) {
        int i=0;//index
        int res=0;//cloud num
        int cnt=0;//count of cloud num
        for(i=left;i<=right;++i){
            if(num[i]==res){
                ++cnt;
            }else{
                if(cnt--==0){
                    cnt = 1;
                    res = num[i];
                }
            }
        }
        for(i=left,cnt=0;i<=right;++i){
            if(num[i]==res)++cnt;
        }
        return cnt<threshold ? -1:res;
    }

    public static void main(String[] args) {
        int[] tmp = {1,1,2,2,1,1};
        MajorityChecker majorityChecker = new MajorityChecker(tmp);
        System.out.println(majorityChecker.query(0,5,4)); // 返回 1
        System.out.println(majorityChecker.query(0,3,3)); // 返回 -1
        System.out.println(majorityChecker.query(2,3,2)); // 返回 2

    }
}

法二:
摩尔投票+线段树，可以实现O(logn)的区间查找。
在树的每个节点中，val保存当前区间中可能的众数，cnt保存当前元素的频率（pk之后的）。为了得到某个区间内给定数出现的频率，把数在原数组中出现的下标按升序保存在一个数组中，可以在O(logn)的时间复杂度下确定该数在某个区间内出现的频率。

class MajorityChecker {
private:
    class Node {
    public:
        int val;
        int cnt;
        Node(int val, int cnt):val(val),cnt(cnt) {}
        Node() :val(0), cnt(0) {}
        Node operator+ (const Node& b)const {
            Node res;
            if (val == b.val) {
                res.val = val;
                res.cnt = cnt + b.cnt;
            }
            else if (cnt > b.cnt) {
                res.val = val;
                res.cnt = cnt - b.cnt;
            }
            else {
                res.val = b.val;
                res.cnt = b.cnt - cnt;
            }
            return res;
        }
    };
    vector<Node> tree;
    vector<vector<int>> index;
    vector<int> data;
    int len;
    void build(int node, int start, int end) {
        if (start == end) {
            tree[node].val = data[start];
            tree[node].cnt = 1;
        }
        else {
            int mid = start + end >> 1;
            int left = node << 1;
            int right = (node << 1) + 1;
            build(left, start, mid);
            build(right, mid + 1, end);
            tree[node] = tree[left] + tree[right];
        }
    }

    //find [a,b] in [A,B]
    Node search(int node,int a, int b,int A,int B) {
        if (a == A && b == B) {
            return tree[node];
        }
        else {
            int mid = A + B >> 1;
            if (b <= mid)return search(node << 1, a, b, A, mid);
            if (a > mid)return search((node <<1 )+1,a,b,mid+1,B);
            return search(node << 1, a, mid, A, mid) + search((node << 1) + 1, mid + 1, b, mid + 1, B);
        }
    }
public:
    MajorityChecker(vector<int>& arr) {
        len = arr.size();
        tree = vector<Node>(len * 8 + 1, Node());
        index = vector<vector<int>>(20001);
        data = vector<int>(len);
        for (int i = 0;i < len;++i) {
            index[data[i] = arr[i]].push_back(i);
        }
        build(1, 0, len - 1);
    }

    int query(int left, int right, int threshold) {
        int res = search(1, left, right, 0, len - 1).val;
        vector<int>& ind = index[res];
        if (upper_bound(ind.begin(), ind.end(), right) - lower_bound(ind.begin(), ind.end(), left) < threshold)res = -1;
        return res;
    }
};

参考：
https://leetcode-cn.com/problems/online-majority-element-in-subarray/solution/san-chong-fang-fa-bao-li-fen-kuai-xian-duan-shu-by/
https://leetcode-cn.com/problems/online-majority-element-in-subarray/solution/golang-344ms-xian-duan-shu-er-fen-cha-zhao-by-resa/