在数组中出现超过n/3次的数字

Question

我已经读过这个问题 找到一个数组中最常见的条目

jon双向飞碟的回答只是让人心旷神怡...... :)

现在我试图解决这个问题找到一个在数组中出现超过n/3次的元素.

我很确定我们不能应用相同的方法,因为可能有2个这样的元素会发生超过n/3次并且会给出错误的计数警报.所以我们有什么方法可以调整jon双向飞碟的回答为此工作..？

或者是否有任何解决方案将在线性时间内运行？

Answer 1

Jan Dvorak的回答可能是最好的:

• 从两个空候选槽和两个计数器设置为0开始.
• 对于每个项目:
  • 如果它等于任一候选者,则递增相应的计数
  • 否则,如果有一个空槽(即一个计数为0的槽),则将其放入该槽并将计数设置为1
  • 否则将两个计数器减少1

最后,对阵列进行第二次传递,以检查候选者是否确实具有所需的计数.您链接的问题不允许这样做,但我不知道如何避免这个修改版本.如果某个值超过n/3次,那么它将位于一个插槽中,但您不知道它是哪一个.

如果问题的这个修改版本保证有两个值超过n/3元素(通常,k-1值大于n/k),那么我们就不需要第二遍.但是当原始问题k=2和1保证多数时,我们无法知道我们是否"应该"将其概括为保证1这样的元素或保证k-1.保证越强,问题就越容易.

Answer 2

使用Boyer-Moore多数投票算法,我们得到:

vector<int> majorityElement(vector<int>& nums) {
    int cnt1=0, cnt2=0;
    int a,b;
    for(int n: nums){
        if (cnt1 == 0 || n == a){
            cnt1++;
            a = n;
        }
        else if (cnt2 == 0 || n==b){
            cnt2++;
            b = n;
        }
        else{
            cnt1--;
            cnt2--;
        }
    }
    cnt1=cnt2=0;
    for(int n: nums){
        if (n==a) cnt1++;
        else if (n==b) cnt2++;
    }
    vector<int> result;
    if (cnt1 > nums.size()/3) result.push_back(a);
    if (cnt2 > nums.size()/3) result.push_back(b);
    return result;
}