给定一个包含 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)?
不要使用额外的空间.
推荐答案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 ",current_candidate,counter); } else if (counter == 0) { current_candidate = arr[i]; ++counter; printf("candidate: %i, counter: %i ",current_candidate,counter); } else { --counter; printf("candidate: %i, counter: %i ",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 ", 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
更多推荐
如何找到至少重复 N/2 次的数组元素?
发布评论