查找數組中的多數元素

Question

多數元素是發生超過數組大小的一半的元素。

如何在O(n)中找到數組中的多數元素？

示例輸入：

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

預期輸出：

2 

Answer 1

多數元件（如果存在）也將是中值。我們可以在O（n）中找到中位數，然後檢查它是否是O（n）中的有效多數元素。 更多實施細節link

Answer 2

隨機抽樣方法如何？你可以對sqrt（n）元素進行取樣，對於每個發生超過sqrt（n）/ 4次的元素（可以在O（n）時間和O（sqrt（n））空間中天真地完成），你可以檢查無論它是否是O（n）時間的多數元素。

該方法找到大部分的概率很高，因爲大多數元素在預期中至少被採樣sqrt（n）/ 2次，標準偏差最多爲n^{1/4}/2。

另一種抽樣方法類似於我在其中一個重複鏈接中看到的方法，即繪製兩個樣本，如果相等，則驗證您是否已在O（n）時間內找到多數元素。額外的驗證步驟是必要的，因爲除了大多數以外的其他元素可能並不明顯。

Answer 3

如果您可以創建一個散列表並假定散列條目查找是常量，那麼您只需根據出現次數對每個條目進行hash_map。

您可以通過表格進行第二次通過，得到最高計數的表格，但如果您事先知道表格中的元素數量，那麼您會立即知道第一次通過是否有多數元素當我們達到要素數時。

當然，您甚至不能保證連續出現2個元素的序列，例如1010101010101010101沒有連續的1，但它是多數元素。

我們沒有被告知任何關於元素類型是否存在任何排序，但顯然我們必須能夠比較兩個是否相等。

Answer 4

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

Answer 5

時間：O（n）的

空間：O（n）的

走的樹，計算一個哈希表元素的發生。

時間：爲O（n LG N）或O（n * m個）（取決於所使用的排序）

空間：（1）

排序陣列然後計數的元件的出現。

採訪正確答案：摩爾定律表決算法

時間：O（n）的

空間：O（1）

走列表比較當前數VS當前最好的猜測號碼。如果該數字等於當前最佳猜測數字，則遞增計數器，否則遞減計數器，並且如果計數器達到零，則用當前數字替換當前最佳猜測數字，並將計數器設置爲1.當您到達最後時，電流最佳猜測是候選人數字，再次列出候選人的實例。如果最終計數大於n/2，那麼它是大多數，否則不存在一個。

Answer 6

對給定數組進行排序：O（nlogn）。

如果數組大小爲7，那麼多數元素在陣列中至少會出現上限（7/2）= 4次。

數組排序後，這意味着如果多數元素首先在位置i找到，它也可以在位置i + floor（7/2）（4次出現）找到。

實施例 - 給定陣列A - {7,3,2,3,3,6,3}

排序陣列 - {2,3,3,3,3,6,7}

元素3位於位置1（數組索引從0開始）。如果位置1 + 3 =第4個元素也是3，則表示3是多數元素。

如果我們循環從最初開始陣列..

比較位置0與位置3，不同的元件2和3 比較位置1位置4，相同的元件。我們發現我們的多數比賽！

複雜度 - O（n）

總時間複雜度 - O（n）。

Answer 7

多數元素：

在數組A [] n大小的大多數元件是出現超過n/2的時間（因此存在至多一個這樣的元素）的元素。

找到一個候選人：

爲第一階段的算法，在輸出工作（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] 

以上算法循環通過每個元件並保持的[maj_index]的計數，如果下一個元件是相同的則遞增計數，如果下一個元素是不相同，則遞減計數，並且如果計數達到0然後將maj_index更改爲當前元素並將count設置爲1.第一階段算法爲我們提供了一個候選元素。在第二階段，我們需要檢查候選人是否真的是多數人。

第二階段很簡單，可以很容易地在O（n）中完成。我們只需要檢查候選元素的計數是否大於n/2。

閱讀geeksforgeeks更多細節

Answer 8

在蒙特卡洛算法，

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

Answer 9

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

時間複雜度爲O（n）

Answer 10

這是可悲的在5年內沒有人寫出正確的答案解釋這個問題。

這是流算法中的一個標準問題（您有一個巨大的（可能無限的）數據流），並且必須計算來自此流的一些統計信息，並通過此流一次。

---

顯然你可以用散列或排序接近它，但有一個潛在的無限流，你可以清楚地耗盡內存。所以你必須在這裏做一些聰明的事情。

---

大多數元件是發生多於陣列的大小的一半的元素。這意味着多數元素出現的次數多於所有其他元素的組合。也就是說，如果您計算多數元素出現的次數，並減去所有其他元素的出現次數，您將得到一個正數。

因此，如果您計算某個元素的出現次數，並減去所有其他元素的出現次數並得到數字0，那麼您的原始元素不能是多數元素。這是正確算法的基礎：

聲明兩個變量counter和possible_element。迭代流，如果計數器爲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 

它清楚地看到，該算法是O(n)具有非常小的恆定O(n)之前（如3）。此外，它看起來像空間複雜性是O(1)，因爲我們只有三個變量初始化。問題是這些變量之一是一個計數器，它可能會長到n（當數組由相同的數字組成時）。而要存儲號碼n則需要O(log (n))空間。所以從理論角度來看它是O(n)時間和O(log(n))空間。 從實際的，你可以在longint中適合2^128的數字，這個數組中的元素數目是無法想象的巨大。

另請注意，該算法僅適用於存在多數元素的情況。如果這樣的元素不存在，它仍然會返回一些數字，這肯定是錯誤的。（很容易修改算法，告訴廣大的元素是否存在）

歷史頻道：這個算法是由博耶，摩爾某處發明於1982年，並呼籲Boyer–Moore majority vote algorithm

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


} 

}

Answer 12

一修改後的版本博耶的算法，

• 3遍，其中，
  • 在第一遍中，我們做了數組的前向迭代
  • 在第二遍中，我們做了數組的反向迭代。
  • 在第三遍中，獲得在第一遍和第二遍中獲得的多數元素的計數。

技術上的線性複雜性的算法（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

Answer 13

感謝啓發我知道Bob Boyer's algo. :)

的Java通用版以前的答案：博耶的算法的修改版本

注：原始類型的陣列可以使用包裝。

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

}

Answer 14

要發現大多數元素的數組中的那麼你可以使用摩爾定律的多數票算法這是它最好的算法之一。

時間複雜度：O(n) or linear time

空間複雜：O(1) or constant space

更多的Moore's Majority Vote Algorithm和GeeksforGeeks

Answer 15

//假設，我們給出一個數組A. //如果我們有給定數組中的每個元素中的所有元素都小於K，那麼我們可以創建一個長度爲K + 1的附加數組B.

//在數組的每個索引處初始化值爲0 //然後迭代給定數組A，對於每個數組值A [i]，在相應索引A [i]處將值遞增爲1 ]在創建的數組B中。

//在遍歷數組A後，現在遍歷數組B並找到最大值。如果您發現值大於n/2，則返回該特定索引。

//時間如果K < = n，則複雜度將爲O（n + K），則等於O（n）。

//我們在這裏有一個約束，這個數組的所有元素都是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)); 
    } 
} 

Answer 16

這將幫助你，如果兩個元素重複相同的次數，如果將顯示沒有。

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) 
{ printf("\n for:%d, %d>%d",a[i],count,temp); 
    temp=count; 
    maj=i; 
} 
else if(count==temp) 
{ printf("\n for:%d, %d=%d, at i=%d",a[i],count,temp,i); 
    maj=-1; 
} 
} 

printf("\n%d",a[maj]); 
return maj; 
}