如何找到重复至少N/2次的数组元素?

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

给定一个有N个元素的数组。我们知道其中一个元素至少会重复N/2次。

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

我们对其他元素一无所知。它们可能会重复，也可能是独一无二的。

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)?

是否有一种方法可以找出在单个通道中至少重复N/2次或可能是O(N)的元素?

No extra space is to be used .

不需要使用额外的空间。

8 个解决方案

#1

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

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

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

这里有一个有趣的解释(至少比读报纸更有趣):http://userweb.cs.utexas.edu/~moore/best ideas/mjrty/index.html。

#2

As the other users have already posted the algorithm, I won't repeat that. However, I provide a simple explanation as to why it works:

由于其他用户已经发布了该算法，我不会重复。然而，我提供了一个简单的解释，解释它为什么起作用:

Consider the following diagram, which is actually a diagram of unpolarized light:

考虑下面的图，它实际上是一个非偏振光的示意图:

Each arrow from the centre represents a different candidate. Imagine a point somewhere on an arrow representing the counter and candidate. Initially the counter is at zero, so it begins in the centre.
When the current candidate is found, it moves one step in the direction of that arrow. If a different value is found, the counter moves one step towards the centre.
If there is a majority value, more than half of the moves will be towards that arrow, and hence the algorithm will end with the current candidate being the majority value.

每个来自中心的箭头代表不同的候选人。假设有一个点在一个箭头上，代表计数器和候选者。最初计数器为零，所以它从中心开始。当找到当前的候选对象时，它会向箭头的方向移动一步。如果发现一个不同的值，计数器向中心移动一个步骤。如果有一个大多数值，那么超过一半的移动将指向那个箭头，因此算法将以当前的候选者为多数值结束。

#3

The Boyer-Moore Majority Vote Algorithm

Boyer-Moore多数投票算法。

//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)

#4

This code is a similar implementation to the way in which we find the majority of an element

这段代码与我们找到大多数元素的方式类似。

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

#5

It doesn't seem possible to count anything without using extra space. You have to store atleast one counter somewhere. If you mean to say you cannot use more than O(n) space then it should be fairly easy.

不使用额外的空间似乎不可能计算任何东西。你必须在某处存储至少一个计数器。如果你的意思是说你不能使用多于O(n)的空间，那就相当容易了。

One way would be to create a second list of only unique objects from the original list. Then, create a third list the same length as the second with a counter for the number of occurrences of each item in the list.

一种方法是创建第二个列表，只列出来自原始列表的唯一对象。然后，创建第三个列表，与第二个列表相同的长度，以计数器显示列表中每个条目的次数。

Another way would be to sort the list then find the largest contiguous section.

另一种方法是对列表进行排序，然后找到最大的连续部分。

#6

Using the modification suggested by ffao to Davi'd reply:

利用ffao对Davi的修改建议:

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

#7

Try this :

试试这个:

#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";
}

#8

The Boyer-Moore Majority Vote Algorithm fails to find correct majority in the below input arrays

在以下输入数组中，Boyer-Moore多数投票算法未能找到正确的多数。

int numbers[SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4};

int数(大小)= { 1、2、3、4、1,2,3,4,1,2,3,4 };

int numbers[SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4,1};

int数(大小)= { 1、2、3、4、1,2,3,4,1,2,3,4,1 };