[LeetCode] 229. Majority Element II

轉自LeetCode

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

<Solution>

Majority Element 的衍生題，這次不保證有解，且 array 有可能是空的

還有一個改變是，最低次數變成 floor(size / 3)

想法如下

• 因為最低次數變成 floor(size / 3)，所以至多會有 2 個 majority element

• 使用 Boyer-Moore Majority Vote Algorithm 來解這個問題

• 因為題目不保證有解，所以最後還是要檢查一下候選人的出現次數是否符合要求

code如下(參考資料)
c++

kotlin