Matsushita's Blog

配列の中のマジョリティーを探す Majority Element in LeetCode

問題

Int型の配列が与えられて、出現回数が配列の要素数過半数以上の物を出力する問題。 必ずマジョリティな要素は存在すると保証されている。

leetcode.com

解き方

HashMapを用いれば時間計算量O(N)で解けるが、空間計算量はO(N)になってしまう。この問題は以下のようにすることで空間計算量O(1)で解くことができる。

ソースコード