[LeetCode] 217. Contains Duplicate

Intuition

• python 으로 문제 풀이를 하기로 했으니 counter 함수를 사용해서 풀이하면 될것같다!

Approach

• counter 함수로 첫번째 풀이를 했는데, time limit exceeded 가 떴음
• 두번째 제출에서는 set 자료구조를 사용해서 풀이
  • set은 중복을 허용 X
  • 주어진 data set을 set에 넣으면 중복이 사라져서 전체 사이즈가 달라짐
  • set의 사이즈와 nums의 사이즈를 비교!

Complexity

Time complexity:

• first attempt:
  • O(N^2)
  • list.count() 함수는 내부적으로 모든 PyObject를 iterate 하고, 주어진 입력값과 compare 하기 때문에 O(N) complexity를 가진다
    • 참고: https://stackoverflow.com/questions/44812468/what-is-the-time-complexity-of-python-lists-count-function
• second attempt:

Space complexity:

• first attempt:
• second attempt:

Code

first attempt

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for num in nums: 
            if (nums.count(num) >= 2): 
                return True 
            else: 
                continue

        return False

second

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

        return len(nums) != len(set(nums))