350. Intersection of Two Arrays II

求两个数组的交集，结果允许有重复

1.常规O(n)解法

public int[] intersect(int[] nums1, int[] nums2) {
    // create res[]
    int[] res = new int[Math.min(nums1.length, nums2.length)];
    // create a map for nums1
    Map<Integer, Integer> map = new HashMap<>(); // element, count
    for (int i : nums1) {
        map.put(i, map.getOrDefault(i, 0) + 1);
    }

    // check nums2, if count > 0, add to res
    int j = 0;
    for (int i : nums2) {
        if (map.getOrDefault(i, 0) > 0) { // simplify map.containsKey(i) && map.get(i) > 0
            res[j++] = i;
            map.put(i, map.get(i) - 1);
        }
    }

    return Arrays.copyOf(res, j);
}

2.数组指针+inplace复制

public int[] intersect(int[] nums1, int[] nums2) {
    // range boundary here
    if (nums1 == null || nums2 == null) return new int[]{};

    // sort
    Arrays.sort(nums1);
    Arrays.sort(nums2);

    int i, j , k;
    i = j = k = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            i++;
        } else if (nums1[i] > nums2[j]) {
            j++;
        } else {
            nums1[k++] = nums1[i];
            i++;
            j++;
        }
    }
    return Arrays.copyOf(nums1, k);
}