[LeetCode解法] 169. Majority Element

問題の説明

LeetCode 169. Majority Element

リスト内で半数以上を占める要素を見つける。

解法

アプローチ: Two Pointer

1) リストを全体的にトラバースし、辞書を作成する。 2) 辞書の中でn/2以上の回数出現する値を返す。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic = {}
        for i in nums:
            if i not in dic:
                dic[i] = 1
            dic[i] += 1
        
        leng = len(nums)
        for i, v in dic.items():
            if v > leng//2 + 1:
                return i

上記解法の時間複雑度と空間複雑度は次の通りです。

• 時間複雑度: O(N)
  • リストnumsを全体的にトラバースするため、O(N)の時間複雑度がかかります。
• 空間複雑度: O(N)
  • numsのサイズに応じて成長する辞書を使用しているため、追加のO(N)の空間が必要です。