LeetCode-两个数组的交集 II

简介: 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),则会出现数组下标越界

🔎题目链接

两个数组的交集 II

🔎结尾

解法1是楼主自己想的,解法2是楼主参考的LeetCode,解法2比较容易理解

如果大家有什么不太理解的,可以私信或者评论区留言,一起加油

相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
46 0
|
4月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
24 4
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
25 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
71 0
|
2月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
22 0
|
4月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
4月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
4月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组