如何找到被至少N / 2次重复的阵列的元素？

本文介绍了如何找到被至少N / 2次重复的阵列的元素？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

由于具有N个元素的数组。我们知道，这些要素之一至少重演N / 2次。

Given an array with N elements. We know that one of those elements repeats itself at least N/2 times.

我们不知道其他元素任何东西。它们可以重复或可以是唯一的。

We don't know anything about the other elements . They may repeat or may be unique .

有没有办法找出重复至少N / 2次在单通或可以是O元素（N）？

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

没有多余的空间可以使用。

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: %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; }

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

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