leetcode with python:349. Intersection of Two Arrays

题目:

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

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

简单来说就是找出两阵列重複值的set

class Solution:    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:        ans=[]        for i in nums1:            if i in nums2 and i not in ans:                ans.append(i)        return ans

遍历nums1,找出其中在nums2内且尚未被记录的元素
将其纪录至ans,最后回传ans
最后执行时间63ms(faster than 71.99%)

这个方法感觉有点太慢,所以我又改採用双指标的方法

class Solution:    def intersection(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:                if nums1[l] not in ans:                    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
最后执行时间50ms(faster than 90.96%)

而讨论区有人则是直接拿出set的内建函式来实作

class Solution:    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:        return set(nums1).intersection(set(nums2))

将两阵列变为set,回传它们的交集
最后执行时间40ms(faster than 99.31%)

那我们下题见