IntersectionOfTwoArraysII [source code]

public class IntersectionOfTwoArraysII {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length == 0 || nums2.length == 0) return new int[]{};
        List<Integer> res = new ArrayList<>();
        Map<Integer, Integer> dict = new HashMap<>();
        for (int i : nums1) {
            Integer count = dict.get(i);
            if (count == null) dict.put(i, 1);
            else dict.put(i, count + 1);
        }
        for (int i : nums2) {
            Integer count = dict.get(i);
            if (count == null || count == 0) continue;
            else {
                res.add(i);
                dict.put(i, count - 1);
            }
        }
        int end = 0;
        int[] ret = new int[res.size()];
        for (int i : res) ret[end++] = i;
        return ret;
    }
}

这个问题跟 I 基本是差不多的, 就是这里要记录重复了, 不能用 set 了而已.

刚开始想着加速, counts 用的是hash 来解决(value as index), 常规做法是先扫一遍得到 max 和 min, 然后int[]就用max - min + 1作为 size. 但是这个方法被这个 case 给 break 了:

[-2147483648,1,2,3]  
[1,-2147483648,-2147483648]

所以估计还是设计题目的人故意的, 这个好像真没有什么特别好的解决办法;

另外这里用 hashmap 的话, 在第二个循环的时候, 要加一个对于count == 0的判断, 因为光是判断 null 是不够的. 这里还可以用另外一种方法: dict.remove(i). 不过这个方法稍微有点麻烦, 要多判断一下 count 在-1之后是否等于0, 只有等于0以后才能 remove;

速度是6(65), 差强人意.

Problem Description

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?
Difficulty:Easy
Category:Algorithms
Acceptance:44.44%
Contributor: LeetCode
Related Topics
binary search hash table two pointers sort
Similar Questions
Intersection of Two Arrays