LeetCode - 217, Contains Duplicate

[LeetCode] 217. Contains Duplicate

LeetCode 217번 문제를 풀어보았다.. Link

Problem

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Intuition

NeetCode Roadmap의 Arrays & Hashing 영역의 첫번째 문제이다.

난이도는 Easy로, Dictionary에 익숙하다면 쉽게 풀 수 있는 문제라고 생각한다.

List안의 성분을 순회하면서 Dictionary에 넣는데, Dictionary 안에 중복된 key가 있다면 True, 아니면 False를 return하면 된다.

이러면 너무 간단하게 풀리기도 하고, Brute force 방법부터 하나씩 차근차근 살펴보는게 좋을 거 같아서, 총 3개의 접근 방식으로 풀어보았다.

Approach

1. Brute force, List 안에 첫번째 숫자와 다른 숫자들 중 같은게 있는지 하나씩 확인하고 이를 모든 숫자에 대해서 반복한다.
2. List를 Sorting 한 다음 바로 옆에 있는 숫자와 중복되는지 확인한다.
3. Dictionary에 List의 숫자들을 Key로 하여 하나씩 추가하는데, Key가 중복될 경우 True를, 아니면 False를 Return

Complexity

• Time complexity:

  List의 길이를 N이라고 할 때, 각각 O(N^2), O(N log N), O(N)

• Space complexity: 각각 O(1), O(1), O(N)

My Code

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        int_dict = {}
        for num in nums:
            if num in int_dict:
                return True
            else:
                int_dict[num] = 1
        return False

3번 접근방식 (Dictionary)를 활용한 내 코드.. 근데 Neecode씨 영상을 보니까 그냥 set을 쓰더라

간단히 바꿔보면 …

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
       	num_set = {}
        for num in nums:
            if num in num_set:
                return True
            num_set.add(1)
        return False

1번 접근 방식으로 풀어보면

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
    	for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i] == nums[j]:
                    return True
		return False

2번 방식으로 풀어보면

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums_sorted = sorted(nums)
    	for i in range(1, len(nums)):
            if nums_sorted[i-1] == nums_sorted[i]:
                return True
        return False