首页 > 编程语言 >LeetCode算法笔记 350. 两个数组的交集 II

LeetCode算法笔记 350. 两个数组的交集 II

时间:2022-10-10 21:45:47浏览次数:65  
标签:map index int LeetCode II 数组 350 nums1 nums2

import junit.framework.TestCase;

import java.util.Arrays;
import java.util.HashMap;


public class LeetCode03 extends TestCase {
    /**
     * 350. 两个数组的交集 II
     * 给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。
     *
     * 示例 1:
     * 输入:nums1 = [1,2,2,1], nums2 = [2,2]
     * 输出:[2,2]
     *
     * 示例 2:
     * 输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
     * 输出:[4,9]
     *
     * 提示:
     * 1 <= nums1.length, nums2.length <= 1000
     * 0 <= nums1[i], nums2[i] <= 1000
     *
     * 进阶:
     * 如果给定的数组已经排好序呢?你将如何优化你的算法?
     * 如果 nums1 的大小比 nums2 小,哪种方法更优?
     * 如果 nums2 的元素存储在磁盘上,内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
     *
     * 如果nums2的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中。那么就无法高效地对 nums2进行排序,因此推荐使用方法一而不是方法二。
     * 在方法一中,nums2只关系到查询操作,因此每次读取nums2中的一部分数据,并进行处理即可。
     *
     */

    /**
     * 方法一:哈希表
     * 由于同一个数字在两个数组中都可能出现多次,因此需要用哈希表存储每个数字出现的次数。对于一个数字,其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
     * 首先遍历第一个数组,并在哈希表中记录第一个数组中的每个数字以及对应出现的次数,然后遍历第二个数组,对于第二个数组中的每个数字,如果在哈希表中存在这个数字,则将该数字添加到答案,并减少哈希表中该数字出现的次数。
     * 为了降低空间复杂度,首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数,然后遍历较长的数组得到交集。
     *
     * 时间复杂度:O(m+n),其中 m 和 n 分别是两个数组的长度。需要遍历两个数组并对哈希表进行操作,哈希表操作的时间复杂度是 O(1),因此总时间复杂度与两个数组的长度和呈线性关系。
     *
     * 空间复杂度:O(min(m,n)),其中 m 和 n 分别是两个数组的长度。对较短的数组进行哈希表的操作,哈希表的大小不会超过较短的数组的长度。为返回值创建一个数组 tmp,其长度为较短的数组的长度。
     *
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            intersect(nums2, nums1);
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            if (map.containsKey(nums1[i])) {
                map.put(nums1[i], map.get(nums1[i]) + 1);
            } else {
                map.put(nums1[i], 1);
            }
        }
        int[] tmp = new int[nums2.length];
        int index = 0;
        for (int i = 0; i < nums2.length; i++) {
            if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {
                map.put(nums2[i], map.get(nums2[i]) - 1);
                tmp[index++] = nums2[i];
            }
        }
        int[] res = new int[index];
        for (int i = 0; i < index; i++) {
            res[i] = tmp[i];
        }
        return res;
    }

    public int[] intersect2(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            intersect(nums2, nums1);
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums1) {
            Integer count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }

        int[] tmp = new int[nums2.length];
        int index = 0;
        for (int num : nums2) {
            Integer count = map.getOrDefault(num, 0);
            if (count > 0) {
                tmp[index] = num;
                map.put(num, count - 1);
                index++;
            } else {
                map.remove(num);
            }
        }
        return Arrays.copyOfRange(tmp, 0, index);
    }

    /**
     * 方法二:排序 + 双指针
     * 如果两个数组是有序的,则可以使用双指针的方法得到两个数组的交集。
     * 首先对两个数组进行排序,然后使用两个指针遍历两个数组。
     * 初始时,两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字,如果两个数字不相等,则将指向较小数字的指针右移一位,如果两个数字相等,将该数字添加到答案,并将两个指针都右移一位。当至少有一个指针超出数组范围时,遍历结束。
     *
     * 时间复杂度:O(mlogm+nlogn),其中 m 和 n 分别是两个数组的长度。对两个数组进行排序的时间复杂度是 O(mlogm+nlogn),遍历两个数组的时间复杂度是 O(m+n),因此总时间复杂度是 O(mlogm+nlogn)。
     * 空间复杂度:O(min(m,n)),其中 m 和 n 分别是两个数组的长度。为返回值创建一个数组 res,其长度为较短的数组的长度。不过在 C++ 中,我们可以直接创建一个 vector,不需要把答案临时存放在一个额外的数组中,所以这种实现的空间复杂度为 O(1)。
     *
     */
    public int[] intersect3(int[] nums1, int[] nums2) {

        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int num1Length = nums1.length;
        int num2Length = nums2.length;

        int p1 = 0, p2 = 0;
        int index = 0;
        int[] res = new int[Math.min(num1Length, num2Length)];
        while (p1 < num1Length && p2 < num2Length) {
            if (nums1[p1] > nums2[p2]) {
                p2++;
            } else if (nums1[p1] < nums2[p2]) {
                p1++;
            } else {
                res[index++] = nums1[p1++];
                p2++;
            }
        }
        return Arrays.copyOfRange(res, 0, index);

    }

    public void test() {
        int[] nums1 = {1, 2, 2, 1};
        int[] nums2 = {2, 2};

        System.out.println(Arrays.toString(intersect(nums1, nums2)));
        System.out.println(Arrays.toString(intersect2(nums1, nums2)));
        System.out.println(Arrays.toString(intersect3(nums1, nums2)));

        int[] nums3 = {4, 9, 5};
        int[] nums4 = {9, 4, 9, 8, 4};
        System.out.println(Arrays.toString(intersect(nums3, nums4)));
        System.out.println(Arrays.toString(intersect2(nums3, nums4)));
        System.out.println(Arrays.toString(intersect3(nums3, nums4)));

    }

}

  

标签:map,index,int,LeetCode,II,数组,350,nums1,nums2
From: https://www.cnblogs.com/sueyyyy/p/16777493.html

相关文章

  • YII框架的自定义布局(嵌套式布局,版本是1.1.20)
    0x01创建控制器0x02创建文件夹,之后创建视图文件0x03浏览器访问cxy/index控制器,验证以上就是使用默认的布局,非常简单,那么如果我不想用YII框架默认的布局呢,我想用自定义的......
  • IIS7.5配置对PHP的支持
    以下环境是Windows server2008R2IIS7.5一般情况下,windows server系统默认是仅支持IIS+asp或IIS+aspx的搭配的,但是有时候我们的网站程序是php的。所以,我们就需要配置......
  • 2022 ICPC 网络赛(II) H Fast Fourier Transform题解
    简要题意给你一棵树,你可以选若干节点为关键点,定义一个选点方案的价值为:所有路径上没有关键点的点对的距离之和。求所有选点方案的价值之和。题解一开始和队友都读错题了......
  • Leetcode 11 -- 贪心
    题目描述最小字典许思路思路来源由于t中的字符后进先出,可以使用一个暂存栈来保存s删除的第一个字符入栈很简单,初始状态下,栈为空,我们可以直接入栈,因此,每次遍历我们......
  • leetCode 27. Remove Element
    [27.RemoveElement][(https://leetcode.cn/problems/remove-element/)思路数组在内存中是连续的,根据此题要求不能删除,而是覆盖暴力解法此题暴力解法是两层for......
  • leetcode-287. 寻找重复数-数组构成的链表
    287.寻找重复数由题中数字都在[1,n]范围内(包括1和n),可知至少存在一个重复的整数。维护一个映射关系f(n)=index->num,其中数组的下标index,数字为num当一......
  • leetcode349.两个数组的交集
    1.题目描述给定两个数组nums1和nums2,返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。2.示例示例1:输入:nums1=[1,2,2,......
  • 【信号发生器】基于quartusii的信号发生器的设计
    1.软件版本Quartusii12.12.本系统主要内容   仿真是用QuartusII12.0软件仿真的,语言是verloghdl,生成矩形波,脉冲波,正弦波,4级m序列(m序列输出一个就行)。程序下载到开......
  • leetcode 236. Lowest Common Ancestor of a Binary Tree 二叉树的最近公共祖先(中等)
    一、题目大意给定一个二叉树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树T的两个节点p、q,最近公共祖先表示为一个节点x,满......
  • IIS设置了歌词为text/plain格式,但是.net core项目还是访问不了,404,是应.net core里没有
     IIS设置了歌词为text/plain格式,但是.netcore项目还是访问不了,404,是应.netcore里没有支持在StartUp静态文件支持里添加上就可以了。varprovider=newFileExtensio......