天天看點

《啊哈!算法》讀書筆記(第九章)——尋找多數元素問題

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

問題:假如現在有一個序列,已知其中一個數的此書超過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)。

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

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

《啊哈!算法》讀書筆記(第九章)——尋找多數元素問題

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

繼續閱讀