리트코드 - 2215. Find the Difference of Two Arrays

https://leetcode.com/problems/find-the-difference-of-two-arrays/description/

Find the Difference of Two Arrays - LeetCode

 

두 개의 0 인덱스 정수 배열 nums1과 nums2가 주어졌을 때, 여기서 크기가 2인 리스트을 반환하도록 한다.

리스트의 각 요소는 주어진 정수 배열의 모든 고유 정수들로 구성되어야 한다.

 

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        res = []
        list1, list2 = set(nums1), set(nums2) # O(n + m)

        res.append(list(list1 - list2)) # O(n)
        res.append(list(list2 - list1)) # O(m)

        return res

 

set1의 각 요소를 순회하며 set2에 존재하지 않는 요소들만을 선택하여 집합을 구성한다. 따라서 이 연산의 시간 복잡도는 set1의 크기에 비례하는 O(N)이 된다.

 

그 이유는 set 함수는 내부적으로 해시 테이블을 사용하여 데이터를 저장하기 때문에 in 연산을 평균 O(1)의 시간 복잡도로 수행할 수 있기 때문이다.