LeetCode 350. Intersection of Two Arrays II题目分析代码

Given two arrays, write a function to compute their intersection. Example:Given nums1 = [1, 2, 2, 1] , nums2 = [2, 2] , return [2, 2] Note: Each element in the result should appear as many times as it shows in both arrays. The result can be in any order. Follow up: What if the given array is already sorted? How would you optimize your algorithm? What if nums1's size is small compared to nums2's size? Which algorithm is better? What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once? Subscribe to see which companies asked this question.

题目

计算两个数组的交

样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

分析

这道题是上一道题的扩展,只是这次要记录重复的元素的个数,这次我们就用一个哈希表,键记录重复元素,值记录重复个数就行了。采用hashset的方法

代码

public class Solution {
    /**
     * @param nums1 an integer array
     * @param nums2 an integer array
     * @return an integer array
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        // Write your code here
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        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);
        }

        List<Integer> results = new ArrayList<Integer>();

        for (int i = 0; i < nums2.length; ++i)
            if (map.containsKey(nums2[i]) &&
                map.get(nums2[i]) > 0) {
                results.add(nums2[i]);
                map.put(nums2[i], map.get(nums2[i]) - 1); 
            }

        int result[] = new int[results.size()];
        for(int i = 0; i < results.size(); ++i)
            result[i] = results.get(i);

        return result;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android机动车

Java 基础(四)——集合源码解析 List

前面我们学习了Iterator、Collection,为集合的学习打下了基础,现在我们来学习集合的第一大体系 List。

854
来自专栏java工会

Java 泛型详解

1695
来自专栏轮子工厂

深入理解Java中的List、Set与Map集合

784
来自专栏xiaoxi666的专栏

codeM美团编程大赛初赛B轮E题

题目描述 给出一个正整数n,我们把1..n在k进制下的表示连起来记为s(n,k),例如s(16,16)=123456789ABCDEF10, s(5,2)=...

1102
来自专栏微信公众号:Java团长

Java 泛型详解

泛型是Java中一个非常重要的知识点,在Java集合类框架中泛型被广泛应用。本文我们将从零开始来看一下Java泛型的设计,将会涉及到通配符处理,以及让人苦恼的类...

1061
来自专栏Petrichor的专栏

tensorflow编程: Variables

tf.moving_average_variables tf.global_variables_initializer tf.local_variabl...

1381
来自专栏于晓飞的专栏

Java Integer 类 解读

Integer 类是Java中最常用的类型,它是原生类型 int 的包装类。在开发中我们基本可以将两者等价。但是,最近在开发中遇到一个 == 与 equals ...

2503
来自专栏书山有路勤为径

栈与队列基础知识

栈,是先进后出的线性表,标准STL的栈包括如下5种操作,设栈S: 1.取出栈顶元素:S.top(); 2.判断栈是否为空:S.empty(); 3.将元素...

742
来自专栏决胜机器学习

PHP数据结构(十二) ——静态查找表​

PHP数据结构(十二)——静态查找表 (原创内容,转载请注明来源,谢谢) 一、概念 1、查找表:由同一类型数据元素构成的集合。 ...

3687
来自专栏有趣的Python

5-Java基础语法-流程控制之循环结构

while循环;do-while循环;for循环;循环嵌套;break语句;continue语句

1911

扫码关注云+社区