leetcode with python:350. Intersection of Two Arrays II

题目:

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

给定两个阵列,回传里面有两阵列重叠元素的阵列
ex:input:nums1=[1,2,2,1],nums2=[2,2]=>output:[2,2]

这题和349.的差别在于回传阵列的值可以重複
我一开始的想法是建立两个hash map,纪录两阵列元素出现的次数

class Solution:    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:        d1={}        d2={}        ans=[]        for i in nums1:            if i in d1:                d1[i]=d1[i]+1            else:                d1[i]=1                        for i in nums2:            if i in d2:                d2[i]=d2[i]+1            else:                d2[i]=1                        for i in d1:            if i in d2:                x=min(d1[i],d2[i])                ans=ans+[i]*x                    return ans

遍历完两个阵列取得它们的元素对次数的dictionary
若两字典有重複的值,则在两出现次数中取小(x)
在ans内加入x个该元素
最后回传ans即可
最后执行时间45ms(faster than 97.94%)

这题当然也可以用双指标下去解

class Solution:    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:        nums1.sort()        nums2.sort()                l,r=0,0        ans = []        while l <len(nums1) and r <len(nums2):            if nums1[l]<nums2[r]:                l=l+1            elif nums2[r] <nums1[l]:                r=r+1            else:                ans.append(nums1[l])                r=r+1                l=l+1        return ans

先将两阵列排序,设立两个指标(l,r)
一个从nums1头,一个从nums2头开始走
若l位置的值小于r位置的值,l往前走
若l位置的值大于r位置的值,r往前走
若l位置的值等于r位置的值,则于ans纪录该值
直到其中一个指标走到底回传ans
最后执行时间44ms(faster than 98.30%)

那我们下题见