C语言 如何找到至少重复 N/2 次的数组元素？

How to find the element of an array that is repeated at least N/2 times?

提问by Flash

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 .

不会使用额外的空间。

回答by Nabb

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.

中心的每个箭头代表不同的候选人。想象一下代表计数器和候选人的箭头上某处的点。最初计数器为零，因此它从中心开始。
当找到当前候选者时，它会朝那个箭头的方向移动一步。如果找到不同的值，计数器将向中心移动一步。
如果存在多数值，则一半以上的移动将朝向该箭头，因此算法将以当前候选为多数值结束。

回答by David Titarenco

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

回答by st0le

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)

回答by coder101

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

回答by shams

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

回答by srikanth

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

回答by jamesbtate

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.

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

回答by siva

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

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

int numbers[SIZE] = {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};

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

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