どーも！
たかぽんです！
日付跨いでしまったけど...!
引き続きやっていきます！
Majority Element
さて、ではまずは問題について。
問題は以下です。
簡単に説明をしておくと...
リストの中に最も多く入っている要素の値を当てるゲームですね...!
例えば[3,2,3]であれば、3になります。
一応、前提として、Majorityな値は"リストのサイズ/2"より大きくなります。
つまり、リストの半数以上はその値で占めていると想定していいわけですね。
また、Majorityな値は必ず存在する前提で考えて大丈夫です。
なんとなく理解できたかと思います。
それでは、次章でアルゴリズムを検討していきます。
アルゴリズム
さて、まず基本的な考え方としては、リストの要素を一つづつ見ていき、その値のリスト中の数を調べます。
そして、その値がリストの"長さ/2"を超えているならば、その値を返す...と言うふうにすればだいじょうぶそうです。
ここまでをコードにすると...
class Solution:
def majorityElement(self, nums: List[int]) -> int:
for i in nums:
if nums.count(i) > len(nums)/2 :
return i;こんな感じです。
これで提出をしてみると...?
だめでした...
短いテストケースでよければ問題ないのですが、今回のようにめちゃくちゃ長いリストに同じ値が大量にある場合など...TimeLimitExceededと処理に時間がかかり過ぎてエラーになってしまいます。
では、何かしら対策を考えます。
筆者が考えた対策としては、例えば上記の場合、[1,2,1,2,1,2...]となっていて、すごい後ろの方(1万要素あとくらい？)に3が大量にあって、おそらくその3が正解になっていそうでした。
この場合、いかに1,2という重複するものを判定しないようにするか？が大切かなと思います。
そのため、一度確認した値は二度目以降、何も処理せずに無視することにしましょう！
確認済みリストとして"finishedList"を用意して、一度確認をしたら、リストに追加していきます(append)。
そして、毎回処理をする前にその処理済み一覧と現在の要素を比較し、処理済み一覧に存在する場合は何もしないようにします。
逆に、処理済み一覧に存在しない場合のみ、リスト中の個数確認と、半数以上かの確認を行うようにしました。
以上が筆者がたどったアルゴリズム検討でした！
それでは最後に提出コードを載せておきます。
提出コード
Runtime: 160 ms, faster than 86.54% of Python3 online submissions for Majority Element.
Memory Usage: 15.6 MB, less than 52.07% of Python3 online submissions for Majority Element.class Solution:
def majorityElement(self, nums: List[int]) -> int:
finishedList = []
for i, num in enumerate(nums):
if num not in finishedList:
finishedList.append(num)
if nums.count(num) > len(nums)/2 :
return num;
