Leetcode #217. Contains Duplicate

Python set 의 특성을 잘 알고 있으면 상당히 쉽게 풀 수 있다. 

It is easy if you understand set in python. But I was not at the moment so I used Brute force way to solve this problem 

 

Brute force 

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        count = 0
        nums.sort()
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                return True
        return False

As you can see time complexity is O(n) because the code has to loop through all the way to the end of the list.

 

Runtime: 543 ms, Beats 39.44%

Python in function Time Complexity:

• list - Average: O(n)
• set/dict - Average: O(1), Worst: O(n)

Advanced way after understand of Time Complexity of in function in set

 

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

        for el in nums:
            if el in mySet:
                return True
            mySet.add(el)
        return False

Runtime: 477ms, Beats: 42.74%

 

I was able to reduce about 20% of runtime by using set.