【LeetCode】136. 싱글넘버 풀기.

질문으로 연결

문제 개요

비공정수로 구성된 배열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

한 번만 나타나는 정수가 있고 그 외에 두 번

생각

입력nums의 요소整数：出現回数를 앞에서 순서대로 보고 저장하여 각 정수의 출현 횟수를 계수

出現回数=１ 정수 찾기

나는 이 조작을 통해 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에서 사전형dictPython wiki을 사용했습니다.
조작하다
평균 시간 계산량
최차 시간 계산량
key in dict
O(1)
O(n)
되다
파이톤의 사전 형식이 해시표에서 이루어졌기 때문이다[1]
이에 따라 첫 번째for 부분은 O(n*1)=O(n), 두 번째for 부분은 O(n)여서 전체가 O(n)인 것으로 나타났다.
각주
CPython에서 사전은 어떻게 이루어졌습니까디자인 및 히스토리 FAQ-Python 3.9.2 문서 ↩︎