查找出現次數大于n/k的重複元素

本文是對一篇英文論文的總結：Finding Repeated Elements。想看原文，請Google之。

這個問題的簡單形式是“查找出現次數大于n/2的重複元素”。我們先從簡單問題開始，然後再做擴充。

1.查找出現次數大于n/2的重複元素

　　《程式設計之美》中有同樣的一道題《尋找發帖水王》，具體思路是每次删除兩個不同的元素，最後剩下的就是要求的元素。這個結論的證明如下：

　　已知：n,m是正整數，n表示數組的長度，m是出現次數大于n/2的元素的個數，即m>n/2。

　　需要求證的結論包括兩個：

　(1)我們用v表示出現次數大于n/2的元素。當删除兩個不同元素，且其中有一個元素是v時，則m減小1，同時n要減小2。

　　求證：m-1>(n-2)/2    

　　證明：m-1>n/2-1=(n-2)/2

　(2)當删除兩個不同元素，且其中有一個元素不是v時，則隻需要n減小2。

　　求證：m>(n-2)/2 。這個結論是顯然的。

代碼如下：

int find(int array[],　int n)
{
    int candidate;
    int count=0;
    for(int i=0;i<n;++i)
    {
        if(count==0)
        {
             candidate=array[i];count=1;
        }
        else
        {
             if(candidate==array[i])
                   ++count;
              else 
                   --count;   
        }       
    }  
    return candidate;
}      

上述代碼是錯誤的，最後還要驗證一下candiate是不是的出現次數是大于n/2的。反例，1,2,3，最後剩下的是3，但是他不是我們要的結果。

《程式設計之美》的後面習題是“查找出現次數大于n/4的元素”，思路是每次删除不同的4個元素，最後剩下的3個就是候選元素，但是還要驗證這3個元素是否滿足條件。不再詳細解釋。其實《程式設計之美》裡講的方法就是本文後提到的“多重集”算法。