[LeetCode] Single Number

136. Single Number

방법_#1

시간복잡도 O(nlogn)
공간복잡도 O(1)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)

        if (n == 1):
            return nums[0]
        idx = 0

        while (idx < n - 1):
            if (nums[idx] != nums[idx + 1]):
                return nums[idx]
            else:
                idx += 2
        return nums[-1]

방법_#2

시간복잡도 O(n)
공간복잡도 O(n)

import collections

class Solution:
    def singleNumber(self, nums: List[int]) -> int:

        dic = collections.Counter(nums)

        for key in dic:
            if (dic[key] == 1):
                return key

방법_#3

시간복잡도 O(n)
공간복잡도 O(n)

import collections

class Solution:
    def singleNumber(self, nums: List[int]) -> int:

        dic = {}

        for num in nums:
            dic[num] = dic.get(num, 0) + 1 # 키가 존재하지 않을 때 해당 key 의 default 값을 0으로 설정해줌

        for key in dic:
            if (dic[key] == 1):
                return key

시간복잡도 O(n)
공간복잡도 O(1)

 

방법_#4

import collections

class Solution:
    def singleNumber(self, nums: List[int]) -> int:

        ret = 0

        for num in nums:
            ret ^= num
        return ret