[LintCode] 548 Intersection of Two Arrays II 解题报告

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


Notice
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.



Example
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].



Challenge
What if the given array is already sorted? How would you optimize your algorithm?
What if nums1's size is small compared to num2'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?



思路
开一个HashMap。把第一个数组的每一个元素放进表里并统计频率。
遍历第二个数组的每一个元素，并在HashMap里查找，如果查找到了就加入答案列表，并把该元素的频率在HashMap里减1。



Code

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
        
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[] {};
        }
         
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for (int num : nums1) {
            if (!map.containsKey(num)) {
                map.put(num, 1);
            }
            else {
                map.put(num, map.get(num) + 1);
            }
        }
        
        List<Integer> list = new ArrayList<>();
        for (int num : nums2) {
            if (map.containsKey(num) && map.get(num) > 0) {
                list.add(num);
                map.put(num, map.get(num) - 1);
            }
        }
        
        int[] res = new int[list.size()];
        int i = 0;
        for (int num : list) {
            res[i++] = num;
        }
        
        return res;
    }
}