【競技プログラミング】「Single Number」with Python | LeetCode #136

こちらは「Single Number」のPythonによる解答例となっております。この問題は、整数の配列が与えられたときに、配列内の要素のうち、一つだけ出現回数が1回の要素を返す問題です。

問題

整数の配列 nums が与えられたとき、配列内の要素のうち、一つだけ出現回数が1回の要素を返します。

nums には、1つの要素が含まれます。
2 <= nums.length <= 10^4
10^9 <= nums[i] <= 10^9
答えは一意に定まります。

解法

この問題は、ハッシュマップを用いた1つのアプローチがあります。ハッシュマップは、配列内の要素を快速に検索できるため、この問題に適しています。

アルゴリズムの概要を以下に述べます。

ハッシュマップを初期化します。
配列を1つずつ反復処理します。
要素をハッシュマップに追加します。
重複する要素がある場合、ハッシュマップから要素を削除します。
ハッシュマップ内に残った要素を返します。

Pythonコード

以下のコードが、「Single Number」を解くためのPythonプログラムとなります。

### Function ##################################################################

def solve(num=0):
    
    solver  = Solution().singleNumber
    
    if 1 <= num <= Input().input: id_LIST = [num]
    else: id_LIST = [id+1 for id in range(Input().input)]
    
    for id in id_LIST:
        data    = Input(id)
        ans     = solver(data.nums)
        result  = "OK" if ans==data.ans else "NG"
        print(f"[{str(id).zfill(3)}] {result}")

### Class #####################################################################

from functools import reduce
from operator import xor

class Solution(object):

    # def singleNumber(self, nums):
    #     """
    #     :type nums: List[int]
    #     :rtype: int
    #     """
    #     ### return reduce(lambda x, y: x ^ y, nums)
    #     return reduce(xor, nums)

    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        DICT = {}

        for val in nums:
            if val not in DICT: DICT[val] = 1
            else: DICT[val] += 1
        
        return [key for key, val in DICT.items() if val==1][0]
        
        # LIST = []
        
        # for val in nums:
        #     if val not in LIST: LIST.append(val)
        #     else: LIST.remove(val)
        
        # return LIST[0] 

#==============================================================================

class Input:
    
    def __init__(self, num=0):
        
        if num == 1:
            self.nums = [2,2,1]
            self.ans    = 1
        
        elif num == 2:
            self.nums = [4,1,2,1,2]
            self.ans    = 4

        elif num == 3:
            self.nums = [1]
            self.ans    = 1
        
        else:
            self.input  = 3

### Main ######################################################################

if __name__ == "__main__":

    solve()

###############################################################################