217, Contains Duplicate

1. 브루트 포스

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        """brute force
        
        Time Complexity: O(n^2)
        Space Complexity: O(1)

        Returns:
            Time Limit Exceeded
        """
        _len = len(nums)
        for i in range(_len-1):
            temp = nums[i]
            for j in range(i+1, _len):
                if temp == nums[j]:
                    return True
        return False​

 

2. 정렬

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        """sort
        
        파이썬의 내장함수 list.sort()과 sorted(list)는
        Timsort(병합정렬 + 삽입정렬) 알고리즘으로 구현됐으며,
        최악의 경우에서 시간 복잡도는 NlogN이다.

        Time Complexity: O(nlog n) + O(n) = O(nlog n)
        Space Complexity: O(1)

        Returns:
            메모리: 28.26MB
            런타임: 464ms
        """
        nums.sort()
        
        for i, v in enumerate(nums):
            if i == len(nums)-1:
                break
            if v == nums[i+1]:
                return True
        return False​

 

3. hashset

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        """hashset
        
        파이썬 내장함수 set은 중복 허용 X, 순서가 없는 컬렉션이다.
        원소의 읽기, 쓰기, 삭제 등의 연산은 평균적으로 시간 복잡도 O(1)을 가지며,
        set의 합집합, 교집합, 차집합, 대칭차집합 등의 집합 연산은 O(n)의 시간 복잡도를 가진다.

        set은 해시 테이블로 구현돼 있으므로, 원소의 개수에 비례하여 메모리를 사용합니다.
        따라서, O(n)의 공간 복잡도를 가집니다.

        Time Complexity: O(1) * O(n) = O(n)
        Space Complexity: O(n)

        Returns:
            메모리: 31.92MB
            런타임: 421ms
        """
        hashset = set()
        for i in nums:
            if i in hashset:
                return True
            hashset.add(i)
        return False​

 

 

[참고 글]