c - 找出出现次数超过 N/3 的数

Question

有一个大小为N的随机数组，找出出现次数大于N/3的数？例如:

{1,2,14,12,12,15,12,12,8} the result is 12

谁有更有效的算法？我是这样做的:

int getNum(int *arr, int left, int right, const int size)
{
    srand(time(0));
    int index = rand()%(right - left + 1) + left;
    std::swap(arr[left], arr[index]);
    int flag = arr[left];
    int small = left;
    int big = right;
    int equal = left;
    while(equal <= big)
    {
        if(arr[equal] == flag)
        {
            equal++;
        }
        else if(arr[equal] < flag)
        {
            swap(arr[equal++], arr[small++]);
        }
        else
        {
            while(big > equal && arr[big] > flag)
            {
                big--;
            }
            std::swap(arr[big], arr[equal]);
            big--;
        }
    }
    if(equal - small >= (size / 3))
    {
        return arr[small];
    }
    if(small - left >= size/3)
    {
        return getNum(arr, left, small - 1, size);
    }
    if(right - equal + 1 >= size/3)
    {
        return getNum(arr, equal, right, size);
    }
    else
    {
        return -1;
    }
}

首先，我定义了三个标志小等于和大，选择一个数字作为标志，并找到这个数字的正确范围，当 equal - small > size/3 时，这就是我们找到的数字，否则找到大小超过 size/3 的边并递归!

Answer 1

实际上 - there is an algorithm proposed by Karp-Papadimitriou-Shanker通过一次传递查找在数据中出现 1/k 次的项目。当然可以申请k=3。

然而，该算法给出了误报(说某些事情很常见，但实际上并不常见)——但是使用给定的 3 个候选数据对数据进行第二次传递，这些可以很容易地消除。

算法如下:

PF = {}
for each element e:
  if pf.containsKey(e): 
     pf.put(e, pf.get(e)+1) //increase the value by 1
  else:
     pf.put(e,1)
     if pf.size() == k:
         for each key in pf:
              pf.put(key, pf.get(key)-1) //decrease all elements by 1
              if pf.get(key) == 0: //remove elements with value 0
                 pf.remove(key)
output pf

有关上述算法的更多信息和证明可以在 this page 中找到, 幻灯片 8-12

即使有第二遍，算法的复杂度也是 O(n) 时间 O(k) (在你的情况下 k==3 ) 额外的空间。