Leetcode 350：Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

说人话：

求两个数组的交集。

举例1：

举例2：

[法1] Map 记录频次

思路

因为是求交集，所以元素出现的次数是需要进行考虑了。这里笔者考虑到用 Map 这个集合框架来解决这个问题，主要是基于 key-value 的特性。使用 Map 可以记录每个元素出现的频次，然后得出交集。

思路如下：

• 用一个 Map 存下 nums1 数组，并记录下每次元素出现的频次
• 判断 nums2 的元素在 Map 中的出现频次
  • 若 > 0，则说明有，将其放到一个临时数组中，并消耗一个频次；
  • 若 = 0，则说明该元素不在 nums1 中，跳过。
• 复制数组，得到结果

代码

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {

        //记录 nums1 中的元素及其频次
        Map<Integer,Integer> numCount = new HashMap<>();

        for (int i = 0; i < nums1.length; i++) {
            Integer integer = numCount.get(nums1[i]);
            if (integer == null){
                numCount.put(nums1[i],1);
            }else{
                Integer count = numCount.get(nums1[i]);
                numCount.put(nums1[i],++count);
            }
        }

        //临时数组，长度为 nums1 和 nums2 中短的那个
        int[] result = new int[nums1.length<nums2.length?nums1.length:nums2.length];
        //记录交集中的元素个数
        int count = 0;

        //判断 nums2 中每个元素在 nums1 是否存在
        for (int num: nums2){
            Integer i = numCount.get(num);
            if (i != null && i > 0) {
                //存在的话放到临时数组中
                result[count++]=num;
                //然后消耗一个频次
                numCount.put(num,--i);
            }
        }
        
        //复制数组
        int[] r = new int[count];
        for (int i = 0; i < r.length; i++) {
            r[i] = result[i];
        }

        return r;

    }
}

提交结果

代码分析

不考虑集合框架底层原理的话：

• 时间复杂度：O(n)
• 空间复杂度：O(n)