如何find至less重复N / 2次的数组元素？
给定一个包含N个元素的数组。 我们知道其中一个元素至less重复N / 2次。
我们对其他元素一无所知。 他们可能重复或可能是独一无二的。
有没有办法find一次重复至lessN / 2次的元素，或者可能是O（N）？
没有额外的空间可以使用。
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; }
这里有一个有趣的解释（至less比阅读文章更有趣）： http : //userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
由于其他用户已经发布了algorithm，我不会再重复。 不过，我提供一个简单的解释，为什么它的工作原理：
考虑下图，这实际上是非偏振光的图表：
来自中心的每个箭头代表不同的候选人。 想象一下代表柜台和候选人的箭头上的某个点。 最初柜台是零，所以它开始在中心。
当目前的候选人被发现，它向箭头的方向移动一步。 如果发现不同的值，计数器向中心移动一步。
如果存在多数值，超过一半的移动将朝向该箭头，并且因此algorithm将以当前候选者为多数值结束。
Boyer-Moore多数表决algorithm
//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)
这个代码与我们发现大多数元素的方式类似
int find(int* arr, int size) { int count = 0, i, m; for (i = 0; i < size; i++) { if (count == 0) m = arr[i]; if (arr[i] == m) count++; else count--; } return m; }
没有使用额外的空间似乎不可能计算任何东西。 你必须在某处存放至less一个柜台。 如果你的意思是说你不能使用多于O（n）的空间，那么它应该相当容易。
一种方法是从原始列表中仅创build唯一对象的第二个列表。 然后，创build第三个列表，其长度与第二个列表中的每个项目的出现次数相同。
另一种方法是sorting列表，然后find最大的连续部分。
使用ffao提出的对Davi'd回复的修改：
public class MaxRepeated { public static void main(final String[] args) { maxRepeatedElement(new int[]{1, 2, 1, 2, 3, 2, 3, 1}); maxRepeatedElement(new int[]{1, 2, 1, 2, 3, 1, 3, 1}); maxRepeatedElement(new int[]{1, 2, 1, 2, 4, 1, 1, 3, 1, 3, 1}); maxRepeatedElement(new int[]{1, 2, 1, 2, 2, 1, 2, 3, 1, 2, 1, 2}); } private static int maxRepeatedElement(final int[] arr) { int current_candidate = arr[0]; int previous_candidate = arr[0]; int counter = 0, i; for (i = 0; i < arr.length; ++i) { if (current_candidate == arr[i]) { ++counter; } else if (counter == 0) { previous_candidate = current_candidate; current_candidate = arr[i]; ++counter; } else { --counter; } System.out.printf(" candidate: %d, counter: %d\n", current_candidate, counter); } if (counter == 0) { System.out.printf(" possible: %d or %d with net freq %d \n", current_candidate, previous_candidate, counter); final int f1 = frequency(arr, current_candidate); final int f2 = frequency(arr, previous_candidate); final int halfLen = arr.length / 2 + (arr.length % 2 == 0 ? 0 : 1); if (f1 >= halfLen || f2 >= halfLen) { if (f1 > f2) { System.out.printf("majority: %d with freq %d \n", current_candidate, f1); } else { System.out.printf("majority: %d with freq %d \n", previous_candidate, f2); } } else { System.out.printf("NO majority! \n"); } } else { System.out.printf("majority: %d with freq %d \n", current_candidate, frequency(arr, current_candidate)); } return current_candidate; } private static int frequency(final int[] arr, final int candidate) { int counter = 0; for (int c : arr) { counter += candidate == c ? 1 : 0; } return counter; } }
尝试这个 ：
#include<iostream> using namespace std; int main() { int counter=0; int a[]={10, 11, 5, 27, 4, 2, 7, 5, 7, 11, 9, 5, 5, 4, 10, 7, 5, 3, 7, 5}; for(int i = 0; i < 20; i++) { if(a[i]==5) counter++; } cout << "it appears " << counter << " times"; }
Boyer-Moore多数表决algorithm无法在下面的input数组中find正确的多数
int数字[SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4};
int数字[SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4,1};
