如何找到被至少N / 2次重复的阵列的元素? [英] How to find the element of an array that is repeated at least N/2 times?
问题描述
由于具有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;
}
这是一个有趣的解释(比看报纸更有趣,至少):<一href=\"http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html\">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
这篇关于如何找到被至少N / 2次重复的阵列的元素?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!