1157-子数组中占绝大多数的元素(Online Majority Element In Subarray)

原文链接: https://leetcode-cn.com/problems/online-majority-element-in-subarray

英文原文

Design a data structure that efficiently finds the majority element of a given subarray.

The majority element of a subarray is an element that occurs threshold times or more in the subarray.

Implementing the MajorityChecker class:

MajorityChecker(int[] arr) Initializes the instance of the class with the given array arr.
int query(int left, int right, int threshold) returns the element in the subarray arr[left...right] that occurs at least threshold times, or -1 if no such element exists.

Example 1:

Input
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
Output
[null, 1, -1, 2]

Explanation
MajorityChecker majorityChecker = new MajorityChecker([1, 1, 2, 2, 1, 1]);
majorityChecker.query(0, 5, 4); // return 1
majorityChecker.query(0, 3, 3); // return -1
majorityChecker.query(2, 3, 2); // return 2

Constraints:

1 <= arr.length <= 2 * 10⁴
1 <= arr[i] <= 2 * 10⁴
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
At most 10⁴ calls will be made to query.

中文题目

实现一个 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

通过代码

高赞题解

解法一、暴力

问题分为两个部分：

找出 可能的 绝对众数（不一定存在绝对众数，但存在绝对众数的话找到的一定是绝对众数）和统计这个数出现的次数。

找可能的绝对众数方法很简单，暴力寻找即可（类似于打擂台，具体实现可以看代码，正确性证明略去）。

统计次数也使用暴力统计。

设数组长度为 $n$，询问次数为 $q$，则总时间复杂度为 $O(nq)$，无法通过。

[-C++]
class MajorityChecker {
    int n,a[20005];
public:
    MajorityChecker(vector<int>& arr) {
        n=arr.size();
        for(int i=0;i<n;i++)a[i]=arr[i];
    }
    
    int query(int left, int right, int threshold) {
        int i,j,k;
        j=k=0;
        for(i=left;i<=right;i++)if(a[i]==j)k++;
        else if(k)k--;
        else
        {
            j=a[i];
            k=1;
        }
        for(i=left,k=0;i<=right;i++)if(a[i]==j)k++;
        if(k<threshold)j=-1;
        return j;
    }
};

解法二、分块

针对不同的询问区间长度，使用两种不同的方法。取一个分界值 $s$。

如果区间长度 $\leq s$，直接暴力即可。时间复杂度为 $O(s)$。

如果区间长度 $>s$，则绝对众数出现次数 $>\frac{s}{2}$，因此可能的答案个数 $\leq\frac{2n}{s}$（出现次数 $>\frac{s}{2}$ 的不同数字个数 $\leq\frac{2n}{s}$）。

统计每个前缀内这些数各自出现了多少次。询问时枚举每一个可能的数，对两个前缀和求差即可得到这个数在区间内的出现次数。时间复杂度为 $O(\frac{2n}{s})$。

取 $s=\sqrt{2n}$（考虑到常数，实践中不一定最优），两种方法时间复杂度均为 $O(\sqrt{2n})=O(\sqrt{n})$。因此总时间复杂度为 $O((n+q)\sqrt{n})$。可以通过本题。

[-C++]
class MajorityChecker {
    int n,N,s,a[20005],b[205][20005],d[205];
    map<int,int> m;
public:
    MajorityChecker(vector<int>& arr) {
        n=arr.size();
        N=0;
        for(int i=0;i<n;i++)m[a[i]=arr[i]]++;
        s=sqrt(n*2);
        for(auto i:m)if(i.second>s>>1)
        {
            b[++N][0]=0;
            d[N]=i.first;
            for(int j=0;j<n;j++)b[N][j+1]=b[N][j]+(a[j]==d[N]);
        }
    }
    
    int query(int left, int right, int threshold) {
        int i,j,k;
        if(right-left<=s)
        {
            j=k=0;
            for(i=left;i<=right;i++)if(a[i]==j)k++;
            else if(k)k--;
            else
            {
                j=a[i];
                k=1;
            }
            for(i=left,k=0;i<=right;i++)if(a[i]==j)k++;
            if(k<threshold)j=-1;
            return j;
        }
        for(i=1;i<=N;i++)if(b[i][right+1]-b[i][left]>=threshold)return d[i];
        return -1;
    }
};

解法三、线段树

注意到暴力算法维护的信息满足可加性（即可以快速合并两个子段的信息得到完整段的信息），因此可以使用线段树维护。具体实现可以参见代码。因此寻找可能的绝对众数的时间复杂度为 $O(\log n)$。

数值范围是 $[1,20000]$，因此使用 $20000$ 个 vector 存储每一个数出现的位置，使用 lower_bound 和 upper_bound 即可在 $O(\log n)$ 的时间复杂度内找出一个数在一个区间内的出现次数。

因此，单次询问的时间复杂度为 $O(\log n)$，预处理时间复杂度为 $O(n)$，总时间复杂度为 $O(n+q\log n)$。（貌似由于常数 + 数据原因，分块比线段树还快）

[-C++]
class MajorityChecker {
    struct node
    {
        int x,y;
        node operator+(const node& b)const
        {
            node t;
            if(x==b.x)
            {
                t.x=x;
                t.y=y+b.y;
            }
            else if(y<b.y)
            {
                t.x=b.x;
                t.y=b.y-y;
            }
            else
            {
                t.x=x;
                t.y=y-b.y;
            }
            return t;
        }
    }t[65536];
    int n,a[20005];
    vector<int> s[20005];
    void build(int R,int l,int r)
    {
        if(l==r)
        {
            t[R].x=a[l];
            t[R].y=1;
            return;
        }
        int mid=l+r>>1;
        build(R<<1,l,mid);
        build(R<<1|1,mid+1,r);
        t[R]=t[R<<1]+t[R<<1|1];
    }
    node ask(int R,int l,int r,int l1,int r1)
    {
        if(l1==l&&r==r1)return t[R];
        int mid=l+r>>1;
        if(r1<=mid)return ask(R<<1,l,mid,l1,r1);
        if(l1>mid)return ask(R<<1|1,mid+1,r,l1,r1);
        return ask(R<<1,l,mid,l1,mid)+ask(R<<1|1,mid+1,r,mid+1,r1);
    }
public:
    MajorityChecker(vector<int>& arr) {
        n=arr.size();
        int i;
        for(i=0;i<n;i++)s[a[i]=arr[i]].push_back(i);
        build(1,0,n-1);
    }
    
    int query(int left, int right, int threshold) {
        int ans=ask(1,0,n-1,left,right).x;
        if(upper_bound(s[ans].begin(),s[ans].end(),right)-lower_bound(s[ans].begin(),s[ans].end(),left)<threshold)ans=-1;
        return ans;
    }
};

统计信息

通过次数	提交次数	AC比率
3179	9889	32.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途