Intersection of Two Arrays II 548

Question

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?

用sort的方法。

What if nums1's size is small compared to num2's size? Which algorithm is better?

只对num1排序，然后用binary search。

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?

分段取

Solution

和Intersection of Two Arrays类似，但是这题要求答案数组中要出现和原数组中相等数量的重复元素（两个数组中重复元素出现次数少的那个）。

第一种方法同样可以利用sort之后再比较，但是这次不用考虑答案数组中是否包含重复元素。

第二种方法可以利用HashMap，将两个数组中元素和重复次数分别存入两个HashMap，然后去两个HashMap中的重复元素和其中重复次数小的作为答案。

代码如下：

Sort

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
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        ArrayList<Integer> res = new ArrayList<Integer>();
        int i = 0;
        int j = 0;
        while(i < nums1.length && j < nums2.length){
            if(nums1[i] == nums2[j]){
                res.add(nums1[i]);
                i++;
                j++;
            }else if(nums1[i] < nums2[j]){
                i++;
            }else{
                j++;
            }
        }

        int[] result = new int[res.size()];
        int count = 0;
        for(int item : res){
            result[count++] = item;
        }

        return result;
    }
}

HashMap version1

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
        //hashmap version
        HashMap<Integer, Integer> map1 = new HashMap<Integer, Integer>();
        for(int i = 0; i < nums1.length; i++){
            if(!map1.containsKey(nums1[i])){
                map1.put(nums1[i], 1);
            }else{
                map1.put(nums1[i], map1.get(nums1[i]) + 1);
            }
        }

        HashMap<Integer, Integer> map2 = new HashMap<Integer, Integer>();
        for(int i = 0; i < nums2.length; i++){
            if(!map2.containsKey(nums2[i])){
                map2.put(nums2[i], 1);
            }else{
                map2.put(nums2[i], map2.get(nums2[i]) + 1);
            }
        }

        ArrayList<Integer> res = new ArrayList<Integer>();
        for(int key : map2.keySet()){
            if(map1.containsKey(key)){
                int count = Math.min(map1.get(key), map2.get(key));
                while(count != 0){
                    res.add(key);
                    count--;
                }
            }
        }

        int[] result = new int[res.size()];
        int count = 0;
        for(int i : res){
            result[count++] = i;
        }

        return result;
    }
}

HashMap version2

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;
    }
}