leetcode 两个数组的交集II

两个数组的交集 II

题目描述：

给定两个数组，编写一个函数来计算它们的交集。 示例 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 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

问题分析：

数组的交集，也就是两个数组都含有的元素，其中包括元素出现的个数 通过List对象，对数据进行寻找后的删除，插入操作，完成交集数据采集 关于排序优化，从小到大进行比较，利用大小关系进行索引值++,借助List完成数据存储，然后进行向数组的转化

代码展示(已验证)：

//leetcode 350.两个数组的交集II import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class intersect { public static void main(String[] args) { int[] nums1 = {4,9,5}; int[] nums2 = {9,4,9,8,4}; int[] nums = intersect(nums1,nums2); for(int num:nums) System.out.print(num+" "); System.out.print("\n"); int[] nums3 = intersect(nums1,nums2); for(int num:nums3) System.out.print(num+" "); // System.out.println("两个数组的交集如下: "+intersect(nums1,nums2).toString()); }

第一种方法，使用两个list寻找交集数据

// 第一种方法，使用两个list寻找交集数据 static int[] intersect(int[] nums1,int[] nums2) { //将nums1数组的元素赋值给list1 List<Integer> list1 = new ArrayList<Integer>(); for(int num : nums1) list1.add(num); // 创建list2 用来存储两个数组共同拥有的元素 List<Integer> list2 = new ArrayList<Integer>(); for(int num:nums2) { if(list1.contains(num)) { list2.add(num); // 添加 list1.remove(Integer.valueOf(num)); // 删除已经添加的值 // list1.remove(num); // Unknown Source } } // 最后return 数组，所以把交集元素复制给数组 int[] nums = new int[list2.size()]; int i=0; for(int num : list2) { nums[i++] = num; } return nums; }

第二种方法：排序处理

//第二种方法：排序处理 static int[] intersect2(int[] nums1,int[] nums2) { //排序 Arrays.sort(nums1); Arrays.sort(nums2); // 创建一个新的数组用来存储相交的数据 List<Integer> list = new ArrayList<>(); //排序后从小到大进行数据的比较，同时兼顾单一元素出现的次数与数组不同长度的影响 for(int i=0,j=0;i<nums1.length && j<nums2.length;) { if(nums1[i]<nums2[i]) i++; else if(nums1[i]>nums2[i]) j++; else { list.add(nums1[i]); i++; j++; } } //将list中的元素转给数组，return出来 int[] res = new int[list.size()]; for(int i=0;i<list.size();i++) { res[i] = list.get(i);//.get(index)方法，根据索引寻找元素值 } return res; } }

python3：Colletions.Counter

class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: c1, c2 = collections.Counter(nums1), collections.Counter(nums2) res = [] for i in c1 & c2: res += [i] * min(c1[i], c2[i]) return res

泡泡：

数组的交集，也就是寻找相同的，要注意单个元素出现的次数和数组的长度 注意java中数组与python中数组不同之处