Problem#
題目給你一個陣列 nums
,回傳出現次數超過 $\lfloor \frac{n}{2} \rfloor$ 的的那個數字(眾數)。
想法#
直覺做就是先建表紀錄每個數字出現的次數,接著排序拿最大即可
較困難的是 follow-up 的 $O(1)$ 空間複雜度,看題解才知道有 Boyer-Moore Majority Vote Algorithm 這個算法
AC Code#
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(n)$
Boyer-Moore Majority Vote Algorithm
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(1)$
心得#
原始題目很水,follow-up 沒想到QQ