如何找到重复至少N/2次的数组元素？

Question

给定一个包含N个元素的数组.我们知道其中一个元素至少重复N/2次.

我们对其他元素一无所知.它们可能重复或可能是唯一的.

有没有办法找出在一次通过中重复至少N/2次的元素,或者可能是O(N)？

没有额外的空间可供使用.

Answer 1

由于其他用户已经发布了算法,我不再重复了.但是,我提供了一个简单的解释,说明它的工作原理:

考虑下图,它实际上是非偏振光的图表:

来自中心的每个箭头代表不同的候选者.想象一下箭头上的某个点代表计数器和候选人.最初计数器为零,因此它从中心开始.
当找到当前候选者时,它向该箭头方向移动一步.如果找到不同的值,则计数器向中心移动一步.
如果存在多数值,则超过一半的移动将朝向该箭头,因此算法将以当前候选者为多数值结束.

Answer 2

st0le回答了这个问题,但这是一个5分钟的实现:

#include <stdio.h>

#define SIZE 13

int boyerMoore(int arr[]) {
    int current_candidate = arr[0], counter = 0, i;
    for (i = 0; i < SIZE; ++i) {
        if (current_candidate == arr[i]) {
            ++counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        } else if (counter == 0) {
            current_candidate = arr[i];
            ++counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        } else {
            --counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        }
    }
    return current_candidate;
}

int main() {
    int numbers[SIZE] = {5,5,5,3,3,1,1,3,3,3,1,3,3};
    printf("majority: %i\n", boyerMoore(numbers));
    return 0;
}

这是一个有趣的解释(比阅读论文更有趣,至少):http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

Answer 3

Boyer-Moore多数投票算法

//list needs to have an element with a count of more than n/2 throughout itself for
//this algorithm to work properly at all times.

lst = [1,2,1,2,3,1,3,3,1,2,1,1,1]

currentCount = 0
currentValue = lst[0]
for val in lst:
   if val == currentValue:
      currentCount += 1
   else:
      currentCount -= 1

   if currentCount == 0:
      currentValue = val
      currentCount = 1


print(currentValue)