目次
解いた問題
leetcode 169. Majority Element
numsの中に2つの数字が入っていて、片方が$n/2$以上の個数になることが保証されているから大きいほうを返してねって問題。
空間計算量$O(1)$が求められる。
学び
- 数のカウントを共通の変数で行うことで空間計算量を抑えることができそう。
- 「なんとなく○○だろう」で進みがちであり癖になっている。
- 「達成したいことは何か」「そのために何が必要か」を30秒、「今何を扱っているのか」を30秒考える仕組みが必要。
- 記事に書くことを試そうと考えている。
最初に考えた解法
空間計算量$O(1)$は正直わからなかったのでハッシュマップ使用して数えることに。
ハッシュマップの解説は下記を見てみてね。
https://zenn.dev/zenn_mita/articles/f9811270b871d5
class Solution:
def majorityElement(self, nums: List[int]) -> int:
if not nums:
return None
hashmap = {}
for i in range(len(nums)):
if i not in hashmap:
hashmap[i] = 1
else:
hashmap[i] += 1
if hashmap[i] > (len(nums) // 2):
return hashmap[i]
行けたかなと思ったらエラー。
iはnumのインデックスを表しているのにハッシュマップにiを入れていることが問題。
「なんとなくこうだろう」という感覚で突っ走るタイプなのでこういう問題が起きる。
今後はGoal, How, Whatという形で記事にやること書いてからプログラムを書いていき、自分が何をしたくて何をしているのかを意識できるようにしていきたいと思いました（蛇足
修正したものが下記。
class Solution:
def majorityElement(self, nums: List[int]) -> int:
if not nums:
return None
hashmap = {}
for i in range(len(nums)):
if nums[i] not in hashmap:
hashmap[nums[i]] = 1
else:
hashmap[nums[i]] += 1
if hashmap[nums[i]] > (len(nums) // 2):
return nums[i]
これで正解。
return hashmap[nums[i]]としてバリューを返してしまったのは割愛しました。
ただこれだと空間計算量の条件を満たせないのと、計算速度が遅そうなのが気になるところ。
なのでまたAIに答えを聞いてみた。
正解
下記が正解。
「Boyer-Mooreの多数決アルゴリズム」という名前らしい。
class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate = None
count = 0
for num in nums:
if count == 0:
# 新しい候補を採用
candidate = num
count = 1
elif num == candidate:
# 同じ値なら「票」を増やす
count += 1
else:
# 違う値なら「票」を打ち消す
count -= 1
# 問題文より多数派が必ず存在するので candidate を返して良い
return candidate
やっていることとしては、「必ず多数派が存在する」という特性を生かし、それぞれの個数をつぶし合わせて残ったものを返却するというもの。
肝としては変数そのものを独立して数えるのではなく、共通のcount変数を使用して「潰しあい」をさせることによって空間計算量を$O(1)$で抑えている点。
時間計算量はfirst.pyと同じく$O(n)$ではあるものの、いちいちdictを参照しないことからより早く周りっていそうです。
補足：Boyer-Mooreの多数決アルゴリズムとは
このアルゴリズムは「配列の中で過半数より多く出現する要素を、O(n)時間・O(1)空間で求めるためのアルゴリズム」となっている。
値同士を打ち消しながら1回のループで最も頻出する多数派要素を見つけることができる。
今回の問題だと2値分類になっていましたが、「過半数を超える数値が1つ存在する」という条件さえ守られれば複数値でも正常に働きそうです。
下記がその例。
A, B, C, A, A, D, A, C, A
過半数あればほかの数値でマイナスを食らっても最後に残るのは多数派、という結果になります。
ただ過半数ないと最後の最後で少数派がcandidateに代入されてしまう可能性があるので注意が必要です。
感想
Pythonだとfor num in numsという書き方でリストの中身を回すことができるんだった。
最初に勉強した言語がC、そのあと使っていたのがJavaということでPythonicな書き方に慣れていないように感じます。
今後も続けて慣れていきます！