2017年4月28日 星期五

[LeetCode] 169. Majority Element

轉自LeetCode

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
<Solution>
這題是要找出重複次數超過 floor(size / 2) 的值

想法如下
  • 用 hash map 記錄每個值的出現次數,如果超過 floor(size/2) 就回傳答案
  • 時間複雜度O(n),空間複雜度O(n)
code如下
c++
另一種解法是投票法,時間複雜度依然是 O(n),空間複雜度可以變成 O(1)

想法如下
  • 每個數都投票給自己,如果當前答案就是自己,那票數加 1;如果不是,票數減 1
  • 當 cnt = 0 的時候,先假設答案就是當前的值,並 ++cnt
  • 如果 cnt != 0,那當前的值相等於目前的答案,則 ++cnt;反之,則 --cnt
code如下(參考資料)
c++

kotlin
上面這個想法,還可以改寫成 bit operation 的方式

想法如下
  • 每個位元去計算是 1 多,還是 0 多。如果是 1 多,則最後的答案在此位元就一定是 1;反之則是 0
  • 時間複雜度是O(n),空間複雜度是 O(1)
code如下(參考資料)
c++

沒有留言:

張貼留言