两个数组的交集 II --java
2021/11/8 12:39:48
本文主要是介绍两个数组的交集 II --java,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给定两个数组,编写一个函数来计算它们的交集。
示例 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 的元素存储在磁盘上,内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2y0c2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
第一种双指针:
class Solution { public int[] intersect(int[] nums1, int[] nums2) { int len1 = nums1.length,len2 = nums2.length; ArrayList<Integer> result = new ArrayList<>(); //可变数组 Arrays.sort(nums1); //排序s1和s2 Arrays.sort(nums2); int left = 0,right = 0; //双指针 while(left<len1 && right < len2){ if(nums1[left] != nums2[right]){ if(nums1[left] > nums2[right]){ //不同时比较元素较小的,让小的元素组指针+1 right++; }else{ left++; } }else{ result.add(nums1[left]); //相同的时候同时把指针向后移 left++; right++; } } int index = 0; int[] res = new int[result.size()]; for (int k = 0; k < result.size(); k++) { //遍历可变数组把元素放入整形数组中 res[index++] = result.get(k); } return res; } }
第二种哈希表:
class Solution { public int[] intersect(int[] nums1, int[] nums2) { HashMap<Integer,Integer> map = new HashMap<>(); //哈希表 ArrayList<Integer> result = new ArrayList<>(); for(int i=0;i<nums1.length;i++){ //遍历s1,记录频率 map.put(nums1[i],map.getOrDefault(nums1[i],0) + 1); } for(int j=0;j<nums2.length;j++){ //遍历s2,判断s2元素跟s1元素相等时频率 if(map.getOrDefault(nums2[j],0) > 0){ result.add(nums2[j]); map.put(nums2[j],map.getOrDefault(nums2[j],0) - 1); } } int index = 0; //可变数组转化为整形数组 int[] res = new int[result.size()]; for(int k = 0;k<res.length;k++){ res[k] = result.get(k); } return res; } }
这篇关于两个数组的交集 II --java的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)