由网友(人最怕就是动了情)分享简介：考虑到与N个元素的阵列。我们知道，这些要素之一重演ATLEAST N / 2次。我们不知道其他的元素任何东西。它们可以重复或可以是唯一的。 Given an array with N elements. We know that one of those elements repeats itself atleast...

考虑到与N个元素的阵列。我们知道，这些要素之一重演ATLEAST N / 2次。我们不知道其他的元素任何东西。它们可以重复或可以是唯一的。

Given an array with N elements. We know that one of those elements repeats itself atleast N/2 times . We dont know anything about the other elements . They may repeat or may be unique .

有没有办法找出重复ATLEAST N / 2次，单次或可能是O（N）的元素... ???

Is there a way to find out the element that repeats atleast N/2 times in a single pass or may be O(N) ... ???

P.S：无额外的空间将被用于

P.S : No extra space is to be used .

推荐答案

st0le回答了这个问题，但这里有一个5分钟实现：

st0le answered the question, but here's a 5minute implementation:

#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: %in",current_candidate,counter);
        } else if (counter == 0) {
            current_candidate = arr[i];
            ++counter;
            printf("candidate: %i, counter: %in",current_candidate,counter);
        } else {
            --counter;
            printf("candidate: %i, counter: %in",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: %in", boyerMoore(numbers));
    return 0;
}

这是一个有趣的解释（比读报纸更多的乐趣，至少）：http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

And here's a fun explanation (more fun than reading the paper, at least): http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html