【LeetCode】136. Single Numberを解く

問題へのリンク

問題概要

空でない整数からなる配列numsが与えられ，ある１つの整数を除いて全ての整数は２回現れる．このとき，１度しか現れない例外の整数を探す．

例：

Input : nums = [2,2,1]
Output : 1

制約

• $1 \leq nums.length \leq 3*10^4$
• $-3*10^4 \leq nums[i] \leq 3*10^4$
• １つだけ１度しか現れない整数が存在し，それ以外は２回現れる

考えたこと

1. 入力numsの要素を前から順に見て整数：出現回数のように保存することで各整数の出現回数をカウント
2. 出現回数=１となる整数を探す

この操作をして$O(n)$で結果が得られると考えた．

以上の考え方に基づいた実装は以下のようになる：

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dict = {}
        
        for n in nums:
            if n in dict:
                dict[n] += 1
            else:
                dict[n] = 1
        
        for key, val in dict.items():
            if val == 1:
                return key

補足

上記のコードにおける

  if n in dict:

の部分について，計算量$O(n)$なのではないか？と疑問に思う方もいるかもしれない．

hashには辞書型dictを利用しておりPython wikiによると，

操作	平均時間計算量	最悪時間計算量
key in dict	$O(1)$	$O(n)$

となっている．

これは，Pythonにおける辞書型は，ハッシュテーブルで実装されている^[1]ためである．（ちなみに，計算時間が最悪となるのはハッシュ値が全て同じとき）

従って，1つ目のfor部分は$O(n * 1) = O(n)$，2つ目のfor部分は$O(n)$となるため全体として$O(n)$となる．

脚注

1. CPythonで辞書はどのように実装されていますか？｜デザインと歴史 FAQ - Python 3.9.2 ドキュメント