350. Intersection of Two Arrays II

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?
public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return new int[]{};
        }
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        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);
            }
        }
        ArrayList<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);
            }
        }
        
        /**
        if (nums1 == null || nums2 == null) {
            return new int[]{};
        }
        int index1 = 0;
        int index2 = 0;
        ArrayList<Integer> list = new ArrayList<>();
        while (index1 < nums1.length) {
            while (index2 < nums2.length) {
                if (nums1[index1] > nums2[index2]) {
                    index2++;
                } else if (nums1[index1] < nums2[index2]) {
                    // index1++;
                    break;
                } else {
                    list.add(nums1[index1]);
                    // index1++;
                    index2++;
                    break;
                }
            }
            index1++;
        }
        */
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s