線性時間投票算法。我沒有得到它

當我讀這（Find the most common entry in an array），建議Boyer and Moore's Linear Time Voting Algorithm。線性時間投票算法。我沒有得到它

如果您點擊該網站的鏈接，可以逐步解釋算法的工作原理。對於給定的順序，AAACCBBCCCBCC它提供了正確的解決方案。

當我們向前將指針移到元素e：

如果計數器爲0時，我們設置當前候選至e和我們的計數器設置爲1。

如果計數器不是0，我們根據e是否是當前的候選人，遞增或遞減計數器。

當我們完成後，目前候選人是大多數元素，如果有一大部分。

如果我在一張紙上用這個算法AAACCBB作爲輸入，建議的候選人將成爲乙什麼顯然是錯誤的。

在我看來，有兩種可能性

作者們從來沒有嘗試過任何東西比其他AAACCBBCCCBCC他們的算法，是完全不稱職，應該當場（doubtfull）被解僱。
我明顯錯過了一些東西，必須禁止從Stackoverflow和永遠不允許再觸摸任何涉及邏輯。

注意：這裏是一個來自Niek Sanders的C++ implementation of the algorithm。我相信他正確地實施了這個想法，因此它有同樣的問題（或者不是嗎？）。

來源

2009-04-23 Lieven Keersmaekers

該算法僅適用於集合有多數時 - 超過一半的元素相同。你的例子中的AAACCBB沒有這樣的多數。最常見的字母出現3次，字符串長度爲7。

來源

2009-04-23 09:28:40

發生在每個人。不要太嚴格地執行第2點從你的答案:) – 2009-04-23 09:32:27

帶了我好幾分鐘：P – Blorgbeard 2009-04-23 09:32:54

好吧，現在我明白了。該算法規定「這個算法決定一個序列的哪一個元素是大多數」。一開始就忽略了大部分內容，並且假設它談論出現最多次數的元素。這裏的大部分意味着元素應該至少出現「元素數量」一半的一半！ – texens 2013-09-03 21:00:42

從第一連接SO問題：

與屬性，超過所述陣列中的條目的一半是等於N

從博耶和摩爾頁：

其中序列的元素是在大多數，提供有這樣的元件

這兩種算法都明確假設一個元素出現至少N/2次。（特別注意「多數」與「最常見」不一樣。。「）

來源

2009-04-23 09:31:05

小，但一個重要的除了其他的解釋摩爾定律表決權算法有2個部分 -

運行摩爾定律表決權算法只給你一個候選人爲廣大元素的第一部分公告單詞「候選」在這裏。
在第二部分中，我們需要迭代陣列之上再次，以確定是否該候選發生的時間（即，比尺寸大/ 2次）最大數量。

第一次迭代是找到候選&第二迭代是檢查該元素髮生多數的給定陣列中的次。

所以時間複雜度爲：O(n) + O(n) ≈ O(n)

來源

2013-07-03 13:16:09

我寫了一個C++代碼，該算法

char find_more_than_half_shown_number(char* arr, int len){ 
int i=0; 
std::vector<int> vec; 
while(i<len){ 
    if(vec.empty()){  
     vec.push_back(arr[i]); 
     vec.push_back(1); 
    }else if(vec[0]==arr[i]){ 
     vec[1]++; 
    }else if(vec[0]!=arr[i]&&vec[1]!=0){ 
     vec[1]--; 
    }else{     
     vec[0]=arr[i]; 
    } 
    i++; 
} 
int tmp_count=0; 
for(int i=0;i<len;i++){ 
    if(arr[i]==vec[0]) 
     tmp_count++; 
} 
if(tmp_count>=(len+1)/2) 
    return vec[0]; 
else 
    return -1; 
}

和主要功能爲如下：

int main(int argc, const char * argv[]) 
{ 
    char arr[]={'A','A','A','C','C','B','B','C','C','C','B','C','C'}; 
    int len=sizeof(arr)/sizeof(char); 
    char rest_num=find_more_than_half_shown_number(arr,len); 
    std::cout << "rest_num="<<rest_num<<std::endl; 
    return 0; 
}

來源

2014-01-29 19:35:55 feliciafay

當測試情況下是「 AAACCBB「，該集合沒有多數。因爲沒有元素出現3次以上，因爲「AAACCBB」的長度是7

下面是「博耶的和Moore的線性時間投票算法」代碼：

int Voting(vector<int> &num) { 
     int count = 0; 
     int candidate; 

     for(int i = 0; i < num.size(); ++i) { 
      if(count == 0) { 
       candidate = num[i]; 
       count = 1; 
      } 
      else 
       count = (candidate == num[i]) ? ++count : --count; 
     } 
     return candidate; 
    }

來源

2014-12-23 16:33:09

線性時間投票算法。我沒有得到它

回答

相關問題