45 lines
1.6 KiB
Python
45 lines
1.6 KiB
Python
# Intersection of Two Arrays II
|
|
|
|
class Solution:
|
|
def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
|
|
result = []
|
|
nums1.sort()
|
|
nums2.sort()
|
|
p1, p2 = 0, 0
|
|
while p1 < len(nums1) and p2 < len(nums2):
|
|
if nums1[p1] == nums2[p2]:
|
|
result.append(nums1[p1])
|
|
p1 += 1
|
|
p2 += 1
|
|
elif nums1[p1] < nums2[p2]:
|
|
p1 += 1
|
|
else:
|
|
p2 += 1
|
|
|
|
return result
|
|
|
|
## set을 활용한 풀이
|
|
|
|
from collections import Counter
|
|
|
|
class Solution:
|
|
def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
|
|
result = []
|
|
c_nums1 = Counter(nums1)
|
|
for num in nums2:
|
|
if c_nums1.get(num, 0):
|
|
result.append(num)
|
|
c_nums1[num] -= 1
|
|
return result
|
|
|
|
"""
|
|
걸린 시간: 16분
|
|
|
|
시간 복잡도: len(nums1) = n, len(nums2) = m일때 두 리스트를 정렬하고 전체 요소를 확인하기 때문에 O(nlogn + mlogm)이다.
|
|
|
|
해설: 정렬한 뒤 각 리스트마다 포인터를 두고, 같으면 result로 넣고, 다르다면 작은 것에서 한칸 앞으로 옮기는 아이디어를 활용했다.
|
|
set, dict으로 했을 때는 중복이 사라지기 때문에 이렇게 진행했었는데, 더 나은 풀이로 counter를 쓰면 된다.
|
|
Counter하면 그 길이만큼 시간복잡도이고, 나머지 리스트의 전체 요소를 보며 dict 요소 접근을 하기 때문에 이것도 길이만큼이다.
|
|
따라서 전체 시간복잡도는 O(n+m)이 된다.
|
|
|
|
""" |