描述

计算两个数组的交

注意事项

每个元素出现次数得和在数组里一样
答案可以以任意顺序给出

样例

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

挑战

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?

代码

public class Solution {
    /**
     * @param nums1 an integer array
     * @param nums2 an integer array
     * @return an integer array
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        // 计算nums1[i]出现的次数
        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>();

        // 将nums2中与nums1中相同的数存到results中
        // 每存nums2[i]到result里，hash表里的次数减一
        // 注意对hash表次数为0的越界判断
        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;
    }
}