LeetCode-两个数组的交集 II

2023-07-29 59

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LeetCode-两个数组的交集 II

🔎概述

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

🔎题解

🌻解法1

public int[] intersect(int[] nums1, int[] nums2) {
    //新建一个数组num1，长度1001
    //长度参考题目的提示
        int[] num1 = new int[1001];
        for(int i = 0;i < nums1.length;i++) {
          //将nums1数组中的元素所对应的num1位置的值+1
          //举例  nums1 = {2};
          //将2所对应num1的2下标位置的值+1
            num1[nums1[i]] = num1[nums1[i]] + 1;
        }
    //深拷贝--为了记录两个数组不同下标之间的差值
        int[] num2 = Arrays.copyOf(num1,1001);
        for(int i = 0;i < nums2.length;i++) {
          //如果num1所对应下标的值为0就不用再给其赋值
          //举例  num1 = {0,1} -->那么此时数字0就没有在nums1数组出现过
          //           -->nums2即使出现也不是俩数组的交集
            if(num1[nums2[i]] != 0) {
                num1[nums2[i]] = num1[nums2[i]] + 1;
            }
        }
        //将俩数组的交集的值存放在num3
        int[] num3 = new int[1001];
        //利用pos使num3的下标进行更改
        int pos = 0;
        for (int i = 0; i < num1.length; i++) {
          //num1的下标和num2的下标有差值，表示num2出现了num1种出现的数字（交集）
            if(num1[i] != num2[i]) {
              //count表示差值的大小
              //举例 num1 = {3,2} num2 = {2,1}
              //     num1中0元素出现3次，1元素出现2次
              //     num2中0元素出现2次，1元素出现1次
                int count = num1[i] - num2[i];
                //这里为了寻找元素出现的最小次数
                //举例 num1 = {3} num2 = {1}
                //     num1中0元素出现3次，num2中0元素出现1次
                //     表示数组nums2中出现过2次0元素，数组nums1中出现过1次0元素
                //如果不将count重新赋值，那么0元素将会出现2次，而实际交集只有1个0
                if(num2[i] < count) {
                    count = num2[i];
                }
                while(count != 0) {
                    num3[pos] = i;
                    pos++;
                    count--;
                }
            }
        }
        int[] num4 = new int[pos];
        for (int i = 0; i < pos; i++) {
            num4[i] = num3[i];
        }
        return num4;
}

将nums1的元素对应num1的下标+1

新建一个num2数组，深拷贝num1。利用count判断nums2数组中元素与nums1数组中元素相同出现的次数

如果俩数组均有同一数字，那么出现次数少的就是最终存储的次数

举例：nums1 = {4,9,5} nums2 = {9,4,9,8,4} nums1中元素4出现1次，nums2中元素4出现2次，那么最终只存储1次元素4

🌻解法2

public static int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> list1 = new ArrayList<>();
        for (int x : nums1) {
            list1.add(x);
        }
        List<Integer> list2 = new ArrayList<>();
        for (int x : nums2) {
            if(list1.contains(x)) {
                list2.add(x);
                list1.remove(Integer.valueOf(x));
            }
        }
        int[] nums = new int[list2.size()];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = list2.get(i);
        }
        return nums;
    }

利用集合list1存储nums1中的数据

将nums2中有的数据且集合list1中有的数据添加到集合list2中，同时删除集合list1中的该数据，避免重复

利用nums存储集合list2的数据，返回nums

remove构成了方法的重载，必须进行转换–> list1.remove(Integer.valueOf(x));

不转换调用的是remove(int index)，则会出现数组下标越界