LeetCode350-IntersectionofTwoArraysIIIntersectionofTwoArraysII

题目：给定两个数组，写一个函数来计算它们的交集。给定两个数组，编写一个函数来计算它们的交集。示例1：输入：nums1=[1,2,2,1],nums2=[2,2]输出：[2,2]示例2：输入：nums1=[4,9,5],nums2=[9,4,9,8,4]输出：[4,9]解释：输出结果中每个元素出现的次数应该与两个数组中元素出现的次数相同。我们可以忽略输出结果的顺序。注意：结果中的每个元素出现的次数应与它在两个数组中显示的次数相同。结果可以是任何顺序。高级：如果给定的数组已经排序怎么办？你会如何优化你的算法？如果nums1的大小比nums2小很多，哪种方法更好？如果nums2的元素存储在磁盘上，磁盘内存有限，无法一次将所有元素加载到内存中怎么办？追问：如果给定的数组已经排序了怎么办？你将如何优化你的算法？如果nums1的大小比nums2的大小小怎么办？哪种算法更好？如果nums2的元素存储在磁盘上，内存有限，无法一次将所有元素加载到内存中怎么办？解题思路：暴力解题就不说了。哈希表：使用哈希图查找其中一个数组中每个数字的出现频率。遍历另一个数组，每遇到相同的数，就将其存储频率减一，如果频率为0，则从hashmap中移除。例如：输入nums1=[4,9,5],nums2=[9,4,9,8,4}计算nums1的频率：{4:1,9:1,5:1},Key={4,9,5}遍历nums2：Key中存在9，9频-1为0，将9移出HashMap：{4:1,5:1}Key中存在4，4频-1为0，4被移出HashMap:{5:1}9不存在于Key中，skip8不存在于Key中，skip...输出：{9,4}双指针：首先对两个数组进行排序，定义两个指针i,j,移动指针如果nums1[i]==nums2[j]，那么这个数是共享的。如果不相等，则移动元素值较小的指针。例如：输入nums1=[4,9,5],nums2=[9,4,9,8,4]对nums1=[4,5,9],nums2=[4,4,8,9,9]双指针遍历：[4,5,9],[4,4,8,9,9]^^4=4，存入res=[4]，移动双指针：[4,5,9],[4,4,8,9,9]^^5>4,移动指针到4:[4,5,9],[4,4,8,9,9]^^5<8,移动指针to5的指针：[4,5,9],[4,4,8,9,9]^^9>8，将指针移动到8：[4,5,9],[4,4,8,9,9]^^9=9，存入res=[4,9]，移动双指针：[4,5,9],[4,4,8,9,9]^^超过nums1长度，结束，返回res回答进阶问题：双指针法的主要耗时操作是排序操作的排序算法。对于有序数组，当然要用双指针来解决问题。当一个数组的长度远小于另一个数组的长度时，哈希表更适合解决问题。只需要散列较小数组的元素频率，遍历长数组即可。时间复杂度取决于长数组长度。如果使用双指针方法，对长数组进行排序会消耗更多时间。如果内存有限，只能选择不增加空间复杂度的双指针法或者暴力破解。使用哈希表时最坏的情况：每个数只出现一次，统计HashMap元素出现的频率后，其大小可能大于内存容量。哈希表解决方案：Java:classSolution{publicint[]intersect(int[]nums1,int[]nums2){HashMapmap=newHashMap<>();Listlist=newArrayList<>();//动态数组for(Integernum:nums1)map.put(num,map.getOrDefault(num,0)+1);//统计元素频率for(Integernum:nums2){//遍历另一个数组if(map.containsKey(num)){inttmp=map.get(num)-1;//频率减一if(tmp==0)map.remove(num);//频率为0时，移出HashMapelsemap.put(num,tmp);//否则更新频率list.add(num);//添加动态数组}}//转换为数组并返回int大小=list.size();int[]res=newint[大小];for(inti=0;iList[int]:count=dict(collections.Counter(nums1))#自带库来计数元素出现频率并转为Dict类型res=[]fornuminnums2:#遍历另一个数组ifnumincount:count[num]-=1#词频减一res.append(num)ifcount[num]<=0:#当词频为0时，移动出字典count.pop(num)returnres双指针问题解决：Java:classSolution{publicint[]intersect(int[]nums1,int[]nums2){Listlist=newArrayList<>();Arrays.sort(nums1);//排序数组Arrays.sort(nums2);inti=0,j=0;//定义指针while(inums2[j])j++;//移动较小数的指针else{//如果两个数相等，则为交集，存入动态数组，移动双指针list.add(nums1[i]);我++；j++;}}//转换为数组并返回int[]res=newint[list.size()];对于(intk=0;kList[int]:i,j,nums1_size,nums2_size=0,0,len(nums1),len(nums2)#定义指针，计算数组长度nums1,nums2,res=sorted(nums1),sorted(nums2),[]#排序数组，初始化并返回数组reswhileinums2[j]:#Movepointerjwithsmallervalue+=1else:res.append(nums1[i])#如果值相等，则为交集，移动双指针i+=1j+=1returnres欢迎关注微信。信..公开。民众。编号：爱写Bug