Leetcode 217. 중복이 포함되어 있습니다. DSA - #4

질문 링크

Python || C++ || TypeScript

무차별 접근

이 접근 방식은 매우 간단하므로 이 접근 방식에 많은 시간을 낭비하지 않겠습니다.

하나의 요소를 가져와 다른 모든 요소와 비교합니다.

모든 요소에 대해 이 작업을 수행합니다.

암호

def containsDuplicateMethod1(nums: list[int]) -> bool:
    length = len(nums)
    for i in range(length):
        for j in range(i + 1, length):
            if nums[i] == nums[j]:
                return True
    return False

시간 복잡도: O(n^2)
공간 복잡도: O(1)

정렬을 사용한 더 나은 접근 방식

중복 요소를 찾아야 하므로 배열을 정렬한 다음 중복 요소를 찾을 수 있습니다.
중복 요소는 서로 인접해 있습니다.

예: nums = [1, 2, 3, 1]
정렬 후: nums = [1, 1, 2, 3]
이제 인접한 요소를 비교하여 중복 요소를 찾을 수 있습니다.

암호

def containsDuplicateMethod2(nums: list[int]) -> bool:
    nums.sort()
    length = len(nums)
    for i in range(length - 1):
        if nums[i] == nums[i + 1]:
            return True
    return False

시간 복잡도: O(nlogn)
공간 복잡도: O(1)

해싱을 사용한 최상의 접근 방식

이 방법도 매우 이해하기 쉽습니다.

세트를 만듭니다.

배열을 순회하고 요소가 Set에 있는지 여부를 확인합니다.

Set에 요소가 있으면 True를 반환합니다.

Set에 요소가 없으면 Set에 요소를 추가합니다.

전체 배열을 탐색하고 중복 요소를 찾지 못하면 False를 반환합니다.

암호

def containsDuplicateMethod3(nums: list[int]) -> bool:
    storage = set()
    for value in nums:
        if value in storage:
            return True
        storage.add(value)

    return False

시간 복잡도: O(n)
공간 복잡도: O(n)

보너스

해싱을 사용한 최상의 접근 방식(한 줄)

def containsDuplicateMethod4(nums: list[int]) -> bool:
    return len(nums) != len(set(nums))