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)
c++
另一種解法是投票法,時間複雜度依然是 O(n),空間複雜度可以變成 O(1)
想法如下
- 每個數都投票給自己,如果當前答案就是自己,那票數加 1;如果不是,票數減 1
- 當 cnt = 0 的時候,先假設答案就是當前的值,並 ++cnt
- 如果 cnt != 0,那當前的值相等於目前的答案,則 ++cnt;反之,則 --cnt
c++
kotlin
上面這個想法,還可以改寫成 bit operation 的方式
想法如下
- 每個位元去計算是 1 多,還是 0 多。如果是 1 多,則最後的答案在此位元就一定是 1;反之則是 0
- 時間複雜度是O(n),空間複雜度是 O(1)
c++
沒有留言:
張貼留言