定義：序列中的多數元素是指在一個元素個數為n的序列中，多數元素出現次數大于[n/2].

尋找元素方法很多：

1.可以暴力搜索，將每個元素都與其他元素作比較，然后統計該元素出現的次數，時間復雜度為O(n2)；

2.可以先排序，然后再統計每個元素出現的次數，時間復雜度為O(nlogn)；

3.可以尋找中間值元素，因為多數元素在序列中必為中間值元素，時間復雜度是O(n)；(尋找中間值元素可以運用尋找第k小元素算法：http://www.cnblogs.com/7hat/p/3411756.html)

這里要介紹第4種方法，時間復雜度也是O(n)，但是隱藏常數會比尋找中間值的方法要小。

算法基于以下觀察：在原序列中去除兩個不同的元素后，那么在原序列中的多數元素在新序列中還是多數元素。

算法基本思路：

(1)在尋找多數元素的過程中，將計數器置1，遇到相同元素則計數器加1，遇到不同元素則計數器減1，一直到計數器等于0或遍歷完整個序列。由此可見，計數器的值表示當前元素抵消掉不同元素后的出現次數；

(2)當計數器在遍歷完整個序列前就已經是0，則忽略掉已經遍歷過的元素(可以看作兩兩抵消不影響序列中的多數元素)，跳到下一個元素然后計數器重新置1，重復上述步驟，一直到遍歷完整個元素；

(3)當遍歷完整個序列后，算法會返回一個值，此時我們還需要檢測一次這個值是否真的是多數元素，即遍歷統計一次。這一步不可或缺。因為上述兩個步驟到了遍歷完序列后必將返回一個值，無論序列有無多數元素。此值存在三種情況，第一，它真的是多數元素；第二，它只是序列后面的某個元素剛好抵消完序列；第三，兩者皆是。我們必須檢測一次。

算法的實現：

基本上和上面思路一樣，這里我給出遞歸代碼和迭代代碼。需要注意的是，因為有可能不存在多數元素，所以需要一個boolean變量來表示是否找到。

public classmajority{private static booleanflag;private static int candidate(int k, int[] A){//find the candidate may be a majority

int i =k;int x =A[k];int count = 1; //indicates the current element occurrences, after offset different elements

while(i < A.length-1 && count > 0){//remove two different elements, the majority element will not change

i ++;if(A[i] ==x){

count++;

}else{

count--;

}

}//there are three cases of x: x is the majority element or x is the last element or both

if(i == A.length-1)returnx;return candidate(i+1, A);

}public static int findMajority(int[] A){//find the majority

int x = candidate(0, A);int count = 0;for(int i = 0; i < A.length; i ++){//Test whether x is really the majority of elements in the array

if(A[i] ==x){

count++;

}

}if(count > A.length/2){

flag= true;returnx;

}else{

flag= false;return 0;

}

}public static int findMajority1(int[] A){//Iteration

int x = 0;for(int i = 0; i < A.length; i ++){int count = 1;

x=A[i];while(i < A.length-1 && count > 0){

i++;if(A[i] ==x){

count++;

}else{

count--;

}

}

}int count = 0;for(int i = 0; i < A.length; i ++){if(A[i] == x)count ++;

}if(count > A.length/2){

flag= true;returnx;

}else{

flag= false;return 0;

}

}public static voidmain(String[] args){int[] A = {2, 3, 2, 4, 2};int x1 =findMajority(A);if(flag){

System.out.println("Found it: " +x1);

}else{

System.out.println("Not found!");

}int x2 =findMajority1(A);if(flag){

System.out.println("Found it: " +x2);

}else{

System.out.println("Not found!");

}

}

}

Java

總結

以上是生活随笔為你收集整理的python寻找多数元素_寻找多数元素的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。