350 Intersection of two arrays II
Original Description: Given two arrays, write a function to compute their intersection. —————————-
- 要求: 给两个数组,找出其重合。
- 返回: 重合部分
- 例子:
- input: [1,2,2,1], [2,2]
- output: [2,2]
Solution
给两数组排序,然后对两数组逐个元素比较,将重合部分放进结果。
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
# check length and sort
if len(nums1) <= len(nums2):
shorter = sorted(nums1)
longer = sorted(nums2)
else:
shorter = sorted(nums2)
longer = sorted(nums1)
# use two pointers in each of the array
s = 0
l = 0
out = []
while s < len(shorter) and l < len(longer):
if shorter[s] <longer[l]:
s += 1
elif shorter[s] > longer[l]:
l += 1
else:
out.append(shorter[s])
s+=1
l+=1
return out