leetcode350-两个数组的交集II

原题

给定两个数组,编写一个函数来计算它们的交集。

输入: 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 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

解法

思想

哈希表,遍历第一个数组的时候把值和出现的次数对应起来,遍历第二个数组的时候可以得出并集。

代码

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i:nums1){
            if(map.containsKey(i)){
                map.put(i,map.get(i)+1);
            }else map.put(i,1);
        }
        int length = 0;
        for(int i:nums2){
            if(map.containsKey(i)){
                if(map.get(i)-1 == 0){
                    map.remove(i);
                }else map.put(i,map.get(i)-1);
                nums1[length] = i;
                length++;
            }
        }
        int[] ret = new int[length];
        System.arraycopy(nums1,0,ret,0,length);
        return ret;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode350-%e4%b8%a4%e4%b8%aa%e6%95%b0%e7%bb%84%e7%9a%84%e4%ba%a4%e9%9b%86ii/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月22日
下一篇 2019年12月24日

相关推荐

  • leetcode1028-从先序遍历还原二叉树

    原题 我们从二叉树的根节点 root 开始进行深度优先搜索。 在遍历中的每个节点处,我们输出 D 条短划线(其中 D 是该节点的深度),然后输出该节点的值。(如果节点的深度为 D,…

    2020年6月18日
    02350
  • leetcode331-验证二叉树的前序序列化

    原题 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。 _9_ / \ 3 2…

    算法 2020年1月26日
    080
  • leetcode876-链表的中间结点

    原题 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例 1: 输入: [1,2,3,4,5] 输出: 此列表中的结…

    算法 2020年3月23日
    080
  • leetcode590-N叉树的后序遍历

    原题 给定一个 N 叉树,返回其节点值的后序遍历。 例如,给定一个 3叉树 : 返回其前序遍历: [5,6,3,2,4,1]. 说明: 递归法很简单,你可以使用迭代法完成此题吗? …

    2020年1月20日
    080
  • leetcode365-水壶问题

    原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升…

    算法 2020年3月21日
    0190
  • leetcode108-将有序数组转换为二叉搜索树

    原题 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数…

    算法 2020年1月18日
    080
  • leetcode76-最小覆盖子串

    原题 给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。 示例: 输入: S = "ADOBECODEBANC", T = "ABC" 输…

    算法 2020年5月23日
    0150
  • 蓝桥杯试题-大小写转换

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   输入一个字符串,将大写字符变成小写、小写变成大写,然后输出 输入格式 acbAB 输出格式 ACBab …

    算法 2020年2月29日
    060
  • leetcode739-每日温度

    原题 根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定一个列表 te…

    算法 2019年12月11日
    0130
  • leetcode75-颜色分类

    原题 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分…

    算法 2020年4月19日
    0220

发表回复

登录后才能评论