《啊哈！算法》讀書筆記（第九章）——尋找多數元素問題

第九章 還能更好嗎？——尋找多數元素問題

問題：假如現在有一個序列，已知其中一個數的此書超過50%，請找出這個數。比如3、3、1、1、3、2、3中，出現次數超過50%的數是3。

答:

方法1：兩兩比較，分别記錄數字的出現次數，2個for循環就可以解決。時間複雜度O(N^2)。

方法2：排序後再重頭到尾掃一遍，用一個count來統計每個數出現的次數，并再用一個變量max來更新count的最大值。排序可以用堆排序或者快排，時間複雜度O(NlogN)。

方法3：排序結束後可以不掃，如果這個數出現的次數大于50%的話，排序之後就應該就是位于n/2位置的那個數。

方法4：用一個數組來記錄每個數出現的次數，就是類似桶排序的方法，數組中最大值的下标就是出現次數超過50%的數。時間複雜度和空間複雜度都是O(M+N)。如果數的大小分布跨度很大，比如1,10000,1000000，這樣會浪費空間，可以采用離散化解決，比如1對應1,2對應10000,3對應1000000。

方法5：選擇一個數作為劃分起點，然後用類似快速排序的方法将小于它的移到左邊，大于它的移到右邊，這樣就将所有的數劃分為兩部分，此時，劃分點所在位置為k。如果k>n/2，那麼繼續用同樣的方法在左邊部分查找；如果k<n/2就在右邊不認查找；k=n/2那麼就是這個數。這樣比之前的快速排序的方法要快一些，估計近似于O(N)。

方法6：“尋找多元素問題”，我們很容易的看出來，在一個序列中如果去掉2個不同的元素，那麼原序列中的出現次數超過50%的數，在新的序列中還是超過50%，是以我們隻要按照序列依次掃描，先把A[0]指派給c，增加個計數器，count = 1；然後向右掃描，如果跟c相同，則count++，不同，那麼count --，這個真是我們從上面那個結論裡得出的，一旦count == 0了，把c指派為A[i+1],count = 1；，重複該過程，直到結束，這個時候，c就是那個超過50%的數。周遊一遍，時間複雜度為O(N)。

學習算法需要多思考！！！學習算法不能一直學學學，要經常停下來總結與回顧，比較算法的應用場景以及可以解決的問題，比較同一問題采用不同算法的性能。

題目是做不完的，算法是複雜多變的。我需要多練習思考問題的方式，而不是一味的多學新知識。

——配圖來源于《啊哈！算法》第九章