Intersection of two arrays II

Posted on

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.
public static int[] intersect(int[] nums1, int[] nums2) {
       
       if (nums1 == null || nums2 == null) {
          return null;
       }
       /* use Hashmap to store the first array, element as the key, the number of existence as the value */
    HashMap<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);
       }
    }

    /* use ArrayList to generate the result */
    List<Integer> list = new ArrayList<Integer>();
    for (int j = 0; j < nums2.length; j++) {
       if (map.containsKey(nums2[j]) && (map.get(nums2[j]) > 0)) {
          list.add(nums2[j]);
          map.put(nums2[j], map.get(nums2[j]) - 1);
       }
    }

    /* convert ArrayList format of result into int[] */
    int[] result = new int[list.size()];
    for (int k = 0; k < list.size(); k++) {
       result[k] = list.get(k);
    }
    return result;
   }

The difference between this problem and Intersection of two arrays (I) is about the duplicate common elements. So cannot use the Set class to store elements anymore.

Here I used HashMap with the element as the key and the times of appearance as the value. Then the value can control how many times this key should be added into the final result integer array. The complexity is still O(m+n).

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