350. Intersection of Two Arrays II

Source link: https://leetcode.com/problems/intersection-of-two-arrays-ii/

Design

The basic idea is to apply a HashMap to record existing times of each element within nums1 and initialize a list to store matched elements of nums1 and nums2.

  1. Initialize a HashMap and traverse through nums1, record the existing times of each element within nums1.
  2. Initialize an ArrayList and traverse through nums2, once if the element matches the key of the map, add the element into the list and decrease the existing times of it within the map.
  3. Transfer elements inside the list into the result array.

Follow-ups

https://leetcode.com/problems/intersection-of-two-arrays-ii/discuss/439955/JAVA-SOLUTION-+-4-FOLLOW-UPS

Implementation

class Solution {
  public int[] intersect(int[] nums1, int[] nums2) {
    if (nums1 == null || nums2 == null) return new int[0];

    HashMap<Integer, Integer> map = new HashMap<>();
    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> list = new ArrayList<>();
    for (int i = 0; i < nums2.length; i++) {
      if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {
        list.add(nums2[i]);
        map.put(nums2[i], map.get(nums2[i]) - 1);
      }
    }

    int[] res = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
      res[i] = list.get(i);
    }

    return res;
  }
}

Time Complexity

Time: $O(n)$ ($O(m + n)$)

Space: $O(n)$ ($O(m + n)$)