题目
给定两个数组, 编写一个函数来计算它们的交集.
示例
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
题目要求:
输出结果中每个元素出现的次数, 应与元素在两个数组中出现的次数一致.
我们可以不考虑输出结果的顺序.
题解
本题提供两种方法, 方法一是利用排序 + 双指针法进行求解, 方法二是利用 HashMap 进行求解. 方法二参考网上实现. 具体看下面解释:
方法一: 先排序数组, 然后根据双指针进行扫描, 将相等的数添加进返回数组. 这种思路可以快速解决原数组是已经排好序的数组的情况.
- class Solution {
- public int[] intersect(int[] nums1, int[] nums2) {
- Arrays.sort(nums1);
- Arrays.sort(nums2);
- List<Integer> list = new ArrayList<>();
- int i = 0;
- int j = 0;
- // 实现双指针扫描部分, 可以快速解决已排好序的求交集问题
- while(i <nums1.length && j < nums2.length){
- if(nums1[i] < nums2[j]){
- i++;
- }
- else if(nums1[i]> nums2[j]){
- j++;
- }
- else{
- list.add(nums1[i]);
- i++;
- j++;
- }
- }
- int[] arr = new int[list.size()];
- for(int k = 0; k <list.size(); ++k){
- arr[k] = list.get(k);
- }
- return arr;
- }
- }
方法二: 将数组中的值作为键, 将出现的次数作为值, 后面进行的工作是在另一个数组中不断的进行判重与减小出现次数, 具体实现看代码
- class Solution {
- public int[] intersect(int[] nums1, int[] nums2) {
- Map<Integer, Integer> map = new HashMap<>(nums1.length);
- // 将 nums1 出现的数值及频次放入映射中
- for (int num : nums1) {
- Integer count = map.get(num);
- if (count == null) {
- map.put(num, 1);
- }
- else {
- map.put(num, ++count);
- }
- }
- List<Integer> list = new ArrayList<>();
- for (int num : nums2) {
- // 获取映射中该数值出现的频次
- Integer count = map.get(num);
- if (count != null && count != 0) {
- list.add(num);
- // 注意每次匹配后, 该数值的频次需要减 1(nums1 和 nums2 匹配的数值的频次要相同)
- map.put(num, --count);
- }
- }
- int[] res = new int[list.size()];
- for (int i = 0; i < list.size(); i++) {
- res[i] = list.get(i);
- }
- return res;
- }
- }
参考: https://leetcode-cn.com/u/angus-liu/
来源: http://www.bubuko.com/infodetail-3280081.html