找到数组中的多数元素

The majority element is the element that occurs more than half of the size of the array.

大多数元素是出现在数组大小一半以上的元素。

How to find the majority element in an array in O(n)?

如何在O(n)中找到数组中的多数元素?

Example input:

示例输入:

{2,1,2,3,4,2,1,2,2}

Expected output:

预期的输出:

2

16 个解决方案

#1

The majority element (if it exists) will also be the median. We can find the median in O(n) and then check that it is indeed a valid majority element in O(n). More details for implementation link

多数元素(如果存在的话)也是中位数。我们可以找到O(n)中的中位数，然后检查它是否确实是O(n)中的有效多数元素。有关实现链接的更多细节

#2

// returns -1 if there is no element that is the majority element, otherwise that element

// funda :: if there is a majority element in an array, say x, then it is okay to discard 
// a part of that array that has no majority element, the remaining array will still have
// x as the majority element

// worst case complexity :  O(n)

int findMajorityElement(int* arr, int size) { 
    int count = 0, i, majorityElement;
    for (i = 0; i < size; i++) {
        if (count == 0)
            majorityElement = arr[i];
        if (arr[i] == majorityElement) 
            count++;
        else
            count--;
    }
    count = 0;
    for (i = 0; i < size; i++)
        if (arr[i] == majorityElement)
            count++;
    if (count > size/2)
        return majorityElement;
    return -1;
}

#3

It is sad to see that in 5 years no one has written a proper explanation for this problem.

令人遗憾的是，在5年的时间里，没有人对这个问题作出恰当的解释。

This is a standard problem in streaming algorithms (where you have a huge (potentially infinite) stream of data) and you have to calculate some statistics from this stream, passing through this stream once.

这是流算法中的一个标准问题(在流算法中，您有大量(可能是无限的)数据流)，并且您必须从流中计算一些统计数据，只通过流一次。

---

Clearly you can approach it with hashing or sorting, but with a potentially infinite stream you can clearly run out of memory. So you have to do something smart here.

显然，您可以使用散列或排序来处理它，但是如果使用一个潜在的无限流，您显然可以耗尽内存。所以你得做点聪明的事。

---

The majority element is the element that occurs more than half of the size of the array. This means that the majority element occurs more than all the other elements combined. That is, if you count the number of times the majority element appears, and subtract the number of occurrences of all the other elements, you will get a positive number.

大多数元素是出现在数组大小一半以上的元素。这意味着大多数元素的出现比所有其他元素加起来都要多。也就是说，如果你数一下大多数元素出现的次数，然后减去所有其他元素出现的次数，你就会得到一个正数。

So if you count the occurrences of some element, and subtract the number of occurrences of all other elements and get the number 0 - then your original element can't be a majority element. This is the basis for a correct algorithm:

因此，如果您计算某个元素的出现次数，并减去所有其他元素的出现次数，得到数字0——那么您的原始元素不能是多数元素。这是正确算法的基础:

Declare two variables, counter and possible_element. Iterate the stream, if the counter is 0 - your overwrite the possible element and initialize the counter, if the number is the same as possible element - increase the counter, otherwise decrease it. Python code:

声明两个变量，计数器和可能元素。迭代流，如果计数器为0——覆盖可能的元素并初始化计数器，如果数字与可能的元素相同——增加计数器，否则减少计数器。Python代码:

def majority_element(arr):
    counter, possible_element = 0, None
    for i in arr:
        if counter == 0:
            possible_element, counter = i, 1
        elif i == possible_element:
            counter += 1
        else:
            counter -= 1

    return possible_element

It is clear to see that the algorithm is O(n) with a very small constant before O(n) (like 3). Also it looks like the space complexity is O(1), because we have only three variable initialized. The problem is that one of these variables is a counter which potentially can grow up to n (when the array consists of the same numbers). And to store the number n you need O(log (n)) space. So from theoretical point of view it is O(n) time and O(log(n)) space. From practical, you can fit 2^128 number in a longint and this number of elements in the array is unimaginably huge.

很明显，这个算法是O(n)，在O(n)之前有一个非常小的常数(像3)，而且看起来空间复杂度是O(1)，因为我们只有三个变量初始化。问题是这些变量中的一个是计数器，它可能会增长到n(当数组包含相同的数字时)。要存储数字n，需要O(log (n))空间。从理论的角度来看，它是O(n)时间和O(log(n))空间。从实用,你可以适应longint 2 ^ 128数字,这个数字数组中的元素是难以想象的巨大。

Also note that the algorithm works only if there is a majority element. If such element does not exist it will still return some number, which will surely be wrong. (it is easy to modify the algorithm to tell whether the majority element exists)

还要注意的是，该算法只在有多数元素的情况下才有效。如果这样的元素不存在，它仍然会返回一些数字，这肯定是错误的。(很容易修改算法来判断是否存在多数元素)

History channel: this algorithm was invented somewhere in 1982 by Boyer, Moore and called Boyer–Moore majority vote algorithm

历史频道:这个算法是1982年Boyer, Moore发明的，叫做Boyer - Moore多数投票算法

#4

Majority Element:

多数元素:

A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

大小为n的数组A[]中的多数元素是出现次数超过n/2次的元素(因此最多出现一个这样的元素)。

Finding a Candidate:

找到一个候选人:

The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

在O(n)中工作的第一阶段的算法被称为摩尔投票算法。该算法的基本思想是，如果我们用所有与e不同的元素来抵消元素e的每一次出现，那么e就会一直存在，如果它是多数元素的话。

findCandidate(a[], size)
1.  Initialize index and count of majority element
     maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
    (a)If a[maj_index] == a[i]
        count++
    (b)Else
        count--;
    (c)If count == 0
        maj_index = i;
        count = 1
3.  Return a[maj_index]

Above algorithm loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1. First Phase algorithm gives us a candidate element. In second phase we need to check if the candidate is really a majority element.

上面的算法循环遍历每个元素并维护一个[maj_index]的计数，如果下一个元素是相同的，则增加计数，如果下一个元素不相同，那么就减少计数，如果计数达到0，那么将maj_index更改为当前元素，将count值设置为1。第一阶段算法给了我们一个候选元素。在第二阶段，我们需要检查候选人是否真的占多数。

Second phase is simple and can be easily done in O(n). We just need to check if count of the candidate element is greater than n/2.

第二阶段很简单，可以在O(n)中轻松完成。我们只需要检查候选元素的计数是否大于n/2。

Read geeksforgeeks for more details

阅读geeksforgeek网站了解更多细节

#5

Time:O(n)

时间:O(n)

Space:O(n)

空间:O(n)

Walk the tree and count the occurrence of elements in a hash table.

遍历树并计算哈希表中元素的出现次数。

Time:O(n lg n) or O(n*m)(depends on the sort used)

时间:O(nlgn)或O(n*m)(取决于所使用的排序)

space:(1)

空间:(1)

sort the array then count occurrences of the elements.

对数组进行排序，然后计算元素出现的次数。

The interview correct answer: Moore’s Voting Algorithm

面试的正确答案:摩尔的投票算法

Time: O(n)

时间:O(n)

Space:O(1)

空间:O(1)

Walk the list compare the current number vs current best guess number. If the number is equal to the current best guess number increment a counter, otherwise decrement the counter and if the counter hits zero replace the current best guess number with the current number and set the counter to 1. When you get to the end the current best guess is the Candidate number, walk the list again just counting instances of the candidate. If the final count is greater than n/2 then it is the majority number otherwise there isn't one.

浏览列表比较当前数字和当前最佳猜测数字。如果数字等于当前最佳猜测数，则增加计数器，否则减少计数器，如果计数器达到0，则将当前最佳猜测数替换为当前数字，并将计数器设置为1。当你到最后的时候，当前最好的猜测是候选人的数量，再次遍历列表，仅仅是数候选人的实例。如果最终计数大于n/2，那么它就是多数数，否则就没有1。

#6

How about a random sampling approach? You could sample, say sqrt(n) elements and for each element that occurred more than sqrt(n) / 4 times (can be accomplished naively in O(n) time and O(sqrt(n)) space), you could check whether it was a majority element in O(n) time.

随机抽样法怎么样?你可以对每个元素进行采样，比如sqrt(n)元素，对于每一个发生次数超过sqrt(n) / 4次的元素(可以在O(n)时间和O(O(n)空间内天真地完成)，你可以检查它在O(n)时间内是否为多数元素。

This method finds the majority with high probability because the majority element would be sampled at least sqrt(n) / 2 times in expectation, with a standard deviation of at most n^{1/4} / 2.

这种方法发现绝大多数有高概率,因为大多数元素将取样至少sqrt(n)/ 2次期望,最多的标准差n ^ { 1/4 } / 2。

Another sampling approach that is similar to an approach I saw in one of the duplicate links is to draw two samples, and if they are equal verify that you have found the majority element in O(n) time. The additional verification step is necessary because the other elements besides the majority may not be distinct.

另一种类似于我在重复链接中看到的方法的抽样方法是抽取两个样本，如果它们相等，则验证您在O(n)时间中找到了大多数元素。额外的验证步骤是必要的，因为除了大多数元素之外的其他元素可能是不同的。

#7

In Monte-Carlo algorithm,

在蒙特卡罗算法,

Majority (a,n)
//a[]-array of 'n' natural numbers
 {
  j=random(0,1,....,n-1)
  /*Selecting the integers at random ranging from 0 to n-1*/
  b=a[j];c=0;
  for k from 0 to n-1 do
   { 
    if a[k]=b then,
    c=c+1;
    }
    return (c>n/2)
   }

#8

To find the majority of an element in an array then you can use Moore's Majority Vote Algorithm which is one of best algorithm for it.

为了找到数组中的大多数元素，你可以使用摩尔的多数投票算法，这是最好的算法之一。

Time Complexity: O(n) or linear time

时间复杂度:O(n)或线性时间

Space Complexity: O(1) or constant space

空间复杂性:O(1)或常数空间

Read more at Moore's Majority Vote Algorithm and GeeksforGeeks

更多地阅读摩尔的多数投票算法和GeeksforGeeks。

#9

If you are allowed to create a hash-table and assume hash-entry lookup is constant you just hash_map each entry against the number of occurrences.

如果允许您创建一个hashtable，并假定hashentry查找是常量，那么只需根据出现的次数对每个条目进行hash_map。

You could do a second pass through the table you get the one with the highest count, but if you know in advance the number of elements in the table, you will know immediately if we have a majority element on the first pass when we hit the required count on the element.

你可以做第二个通过表得到最高的统计,但如果你预先知道表中元素的数量,您将立即知道如果我们有多数元素第一遍当我们点击所需的元素。

You cannot guarantee of course that there is even a sequence of 2 consecutive occurrences of the element eg 1010101010101010101 has no consecutive 1s but it is a majority element.

当然，你不能保证元素连续出现两次的序列如101010101010101010101010101010101没有连续的1，但它是大多数元素。

We are not told anything about whether there is any kind of ordering on the element type although obviously we must be able to compare two for equality.

我们没有被告知元素类型是否有任何排序，尽管很明显我们必须能够比较两个是否相等。

#10

    int majorityElement(int[] num) {
       int major=num[0], count = 1;
       for(int i=1; i<num.length;i++){
           if(count==0){
               count++;
               major=num[i];
           }
           else if(major==num[i]){
                    count++;
           }
           else 
               count--;
   }            
    return major;
}

Time Complexity O(n)

时间复杂度O(n)

#11

public class MajorityElement
    {
       public static void main(String[] args) 
          {
             int arr[]={3,4,3,5,3,90,3,3};

              for(int i=0;i<arr.length;i++)
                {
                  int count=0;
                   int j=0;

                    while(j<arr.length-1)
                     { 
                        if(i==j)
                        j=j+1;
                          if(arr[i]==arr[j])
                            count++;
                          j++;
                                  }

                             if(count>=arr.length/2)
                               {
                              System.out.println("majority element"+arr[i]);
                                   break;
    }
    }


}

}

}

#12

A modified version Boyer's Algorithm,

修改后的Boyer算法，

• 3 passes where,
  • In the first pass, we do a forward iteration of the array
  • 在第一次遍历中，我们对数组进行正向迭代
  • In the second pass, we do a reverse iteration of the array.
  • 在第二步中，我们对数组进行反向迭代。
  • In third pass, get counts for both the majority elements obtained in first and second passes.
  • 在第三轮中，获取在第一和第二轮中获得的多数元素的计数。
• 在第一轮，我们对数组进行正向迭代，在第二轮，我们对数组进行反向迭代。在第三轮中，获取在第一和第二轮中获得的多数元素的计数。

Technically a linear complexity algorithm (O(3n)). I believe this should work for an array with a majority element that occurs at least n/2 times.

技术上是一种线性复杂度算法(O(3n))。我认为对于一个包含至少n/2次的多数元素的数组来说，这是可行的。

#include <iostream>
#include <vector>

template <typename DataType>
DataType FindMajorityElement(std::vector<DataType> arr) {
    // Modified BOYERS ALGORITHM with forward and reverse passes
    // Count will stay positive if there is a majority element
    auto GetMajority = [](auto seq_begin, auto seq_end) -> DataType{
        int count = 1;
        DataType majority = *(seq_begin);
        for (auto itr = seq_begin+1; itr != seq_end; ++itr) {
            count += (*itr == majority) ? 1 : -1;
            if (count <= 0) {   // Flip the majority and set the count to zero whenever it falls below zero
                majority = *(itr);
                count = 0;
            }
        }
        return majority;
    };
    DataType majority1 = GetMajority(arr.begin(), arr.end());
    DataType majority2 = GetMajority(arr.rbegin(), arr.rend());
    int maj1_count = 0, maj2_count = 0;
    // Check if any of the the majority elements is really the majority
    for (const auto& itr: arr) {
        maj1_count += majority1 == itr ? 1 : 0;
        maj2_count += majority2 == itr ? 1 : 0;
    }
    if (maj1_count >= arr.size()/2)
        return majority1;
    if (maj2_count >= arr.size()/2)
        return majority2;
    // else return -1
    return -1;
}

Code tested here

测试代码在这里

#13

Thanks for the previous answers which inspired me to know Bob Boyer's algo. :)

谢谢你之前的回答，这启发了我去了解Bob Boyer的algo。:)

Java generic version: A modified version of Boyer's Algorithm

Java通用版本:Boyer算法的修改版本

Note: array of primitive type could use wrapper.

注意:原始类型数组可以使用包装器。

import com.sun.deploy.util.ArrayUtil;
import com.sun.tools.javac.util.ArrayUtils;

/**
 * Created by yesimroy on 11/6/16.
 */
public class FindTheMajority {

/**
 *
 * @param array
 * @return the value of the majority elements
 */
public static <E> E findTheMajority(E[] array){
    E majority =null;
    int count =0;

    for(int i=0; i<array.length; i++){
        if(count==0){
            majority = array[i];
        }
        if(array[i].equals(majority)){
            count++;
        }else{
            count--;
        }

    }

    count = 0;
    for(int i=0; i<array.length ; i++){
        if(array[i].equals(majority)){
            count++;
        }
    }

    if(count > (array.length /2)){
        return majority;
    }else{
        return null;
    }
}

public static void main(String[] args){
    String[] test_case1 = {"Roy","Roy","Roy","Ane","Dan","Dan","Ane","Ane","Ane","Ane","Ane"};
    Integer[] test_case2 = {1,3,2,3,3,3,3,4,5};

    System.out.println("test_case1_result:" + findTheMajority(test_case1));
    System.out.println("test case1 the number of majority element should greater than" + test_case1.length/2);
    System.out.println();

    System.out.println("test_case2_result:" + findTheMajority(test_case2));
    System.out.println("test case2 the number of majority element should greater than" + test_case2.length/2);
    System.out.println();
}

}

}

#14

//Suppose we are given an array A. //If we have all the elements in the given array such each element is less than K, then we can create an additional array B with length K+1.

//假设我们有一个数组a //如果我们有给定数组中的所有元素，比如每个元素都小于K，那么我们可以创建一个长度为K+1的数组B。

//Initialize the value at each index of the array with 0. //Then iterate through the given array A, for each array value A[i], increment the value with 1 at the corresponding index A[i] in the created array B.

//在数组的每个索引处初始化值为0。//然后遍历给定的数组A，对于每个数组值A[i]，在创建的数组B中对应的索引A[i]处增加1的值。

//After iterating through the array A, now iterate through the array B and find the maximum value. If you find the value greater than the n/2 then return that particular index.

//在遍历数组A之后，现在遍历数组B并找到最大值。如果你发现值大于n/2，那么返回那个特定的索引。

//Time Complexity will be O(n+K) if K<=n then equivalent to O(n).

//时间复杂度为O(n+K)如果K<=n，则等于O(n)

//We have a constraint here that all elements of the array are O(K). //Assuming that each element is less than or equal to 100, in this case K is 100.

//这里有一个约束条件，即数组的所有元素都是O(K)//假设每个元素都小于或等于100，在这种情况下K是100。

import javax.print.attribute.standard.Finishings;
public class MajorityElement {

    private static int maxElement=100;

    //Will have all zero values initially
    private static int arrB[]=new int[maxElement+1];
    static int findMajorityElement(int[] arrA) { 
         int count = 0, i, majorityElement;
         int n=arrA.length;
         for (i = 0; i < n; i++) {
             arrB[arrA[i]]+=1;
         }

         int maxElementIndex=1;
         for (i = 2; i < arrB.length; i++){
             if (arrB[i]>n/2) {
                maxElementIndex=i;
                break;
            }
        }
        return maxElementIndex;
    }`

    public static void main(String[] args) {
         int arr[]={2,6,3,2,2,3,2,2};
         System.out.println(findMajorityElement(arr));
    }
}

#15

This will Help you and if two elements repeat same number of times if will show none.

这将帮助您，如果两个元素重复相同的次数，if将显示为none。

int findCandidate(int a[], int size)
{
int count,temp=0,i,j, maj;

for (i = 0; i < size; i++) {
count=0;      
for(j=i;j<size;j++)
{
    if(a[j]==a[i])
    count++;
}
if(count>temp)
{   
    temp=count;
    maj=i;
}
else if(count==temp)
{   
    maj=-1; 
}
}


return maj;
}

#16

Sort the given array : O(nlogn).

对给定数组进行排序:O(nlogn)。

If the array size is 7, then the majority element occurs atleast ceiling(7/2) = 4 times in the array.

如果数组大小为7，那么大多数元素在数组中至少出现了ceiling(7/2) = 4次。

After the array is sorted, it means that if the majority element is first found at position i, it is also found at position i + floor(7/2) (4 occurences).

数组排序后，它意味着如果第一次在位置i找到多数元素，它也会在位置i + floor(7/2)(4个发生)找到。

Example - Given array A - {7,3,2,3,3,6,3}

示例-给定数组A - {7,3,2,3,3,6,3}

Sort the array - {2,3,3,3,3,6,7}

对数组进行排序——{2,3,3,3,3,3,3,3,3,6,7}

The element 3 is found at position 1 (array index starting from 0.) If the position 1 + 3 = 4th element is also 3, then it means 3 is the majority element.

元素3位于位置1(数组索引从0开始)。如果位置1 + 3 = 4元素也是3，那么表示3是多数元素。

if we loop through the array from beginning..

如果我们从一开始就对数组进行循环。

compare position 0 with position 3, different elements 2 and 3. compare position 1 with position 4, same element. We found our majority match!

比较位置0和位置3，不同元素2和3。比较位置1和位置4，相同的元素。我们找到了最大的对手!

Complexity - O(n)

复杂性- O(n)

Total time complexity - O(n).

总时间复杂度- O(n)