問題描述
給定一個大小為 n
的整數陣列,如何找到出現頻率大於(必須嚴格大於)n/2
的元素?
例如:arr = [1, 1, 2]
,那麼 1
就是出現頻率大於 n/2
的元素。
如果 arr = [1, 1, 3, 4]
,那麼不存在這樣的元素。
Boyer–Moore majority vote algorithm
一個很直覺的方法就是用一個 hash map 計算所有數字出現的頻率,然後找出出現最多次的元素。需要 O(n) 的空間複雜度以及 O(n) 的時間複雜度。但是用 Boyer-Moore algorithm,只要 O(1) 的空間複雜度即可。來看看這個演算法是如何辦到的。
|
|
candidate
是答案的候選人,而 freq
則是 candidate
出現的頻率。
用 arr = [1, 2, 2, 1, 1, 1, 1]
當範例。我在這邊把各個時候的 candidate
跟 freq
寫下來,為了對齊,我只打 can, fre
。arr = [1, 2, 2, 1, 1, 1, 1]
can = [1, 1, 2, 2, 1, 1, 1]
fre = [1, 0, 1, 0, 1, 2, 3]
接下來跟著演算法實際跑一次。i = 0
時,can = 1, fre = 1
,代表目前候選人是 1
,並且出現的頻率為 1
次。i = 1
時,can = 1, fre = 0
,此時頻率變成 0
,代表我們把剛剛的候選人進行配對,也就是配成 [1, 2]
。i = 2
時,can = 2, fre = 1
,代表目前候選人是 2
,並且出現的頻率為 1
。i = 3
時,can = 2, fre = 0
,此時頻率變成 0
,代表我們把剛剛的候選人進行配對,也就是配成 [2, 1]
。i = 4
時,can = 1, fre = 1
,代表目前候選人是 1
,並且出現的頻率為 1
。i = 5
時,can = 1, fre = 2
,代表目前候選人是 1
,並且出現的頻率為 2
。i = 6
時,can = 1, fre = 3
,代表目前候選人是 1
,並且出現的頻率為 3
。
此時跳出迴圈,回傳 1
。
問題是,為什麽這個演算法是正確的呢?
大家可以發現,這個演算法是基於配對進行的。假設陣列中存在頻率出現超過 n/2
的元素,把它叫做 x
,因為 x
的出現頻率超過 n/2
,代表我們可以把 x
跟非 x
的元素進行配對,配對完之後還會剩下 x
沒有配對到。
例如:arr = [1, 2, 2, 1, 1, 3, 1]
,可以配對成 [1, 2], [1, 2], [1, 3]
並且剩下 [1]
沒有配對到。
這個演算法還有一個特殊的地方,就是如果要找到出現頻率大於 n/3
或是 n/4
的元素,可以用一樣的方法找。只需要增加候選人的人數,就可以用一樣的概念解決。此外,還需要再花 O(n) 的時間檢查 candidate 是否為 majority element。
以下是找到出現頻率大於 n/3
的方法
|
|
參考資料