[Algorithm] 217-Contains-Duplicate

https://leetcode.com/problems/contains-duplicate/

Contains Duplicate - LeetCode

 

방법 1. HashSet 이용한 풀이

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        inputNums = set()

        for i in (nums):
            inputNums.add(i)

        if len(inputNums) != len(nums):
            return True
        return False

 

for 문 도는 중간에 HashSet 에 이미 데이터가 들어있는지 확인하는 로직을 추가해 조금 더 개선해보았다.

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        inputNums = set()

        for i in (nums):
        	# 이 로직 추가
            if i in inputNums:
                return True
            inputNums.add(i)

        return False

 

* Time Complexity - O(n)

* Space Complexity - O(n)

 

---

 

방법 2. sorting 을 이용한 풀이

step 1. sorting 함

step 2. for 문 돌면서 i 랑 i+1 번째 같은 지 비교

 

* Time Complexity - O(nLogn)

* Space Complaxity - O(1)

 

 

---

 

결론 - 공간 좀 들더라도 Time Complexity 줄이는 1번이 나은 것 같다