P176 两个数组的交集

描述#

这个题目说的是，给你两个非空数组，你要实现一个函数，来计算它们的交集。

注意，交集中元素的顺序不重要，以什么顺序返回都可以。

比如说，给你的第一个数组是：
1, 4, 4, 2
第二个数组为：
4, 8, 4, 4
这两个数组都包含两个 4，因此它们的交集为：
4, 4

代码#

public class AlgoCasts {

  // Time: O(m+n), Space: O(m+k)
  public int[] intersectHashMap(int[] nums1, int[] nums2) {
    Map<Integer, Integer> counter = new HashMap<>();
    for (int num: nums1) {
      int cnt = counter.getOrDefault(num, 0);
      counter.put(num, cnt+1);
    }
    List<Integer> list = new ArrayList<>();
    for (int num: nums2) {
      int cnt = counter.getOrDefault(num, 0);
      if (cnt > 0) {
        list.add(num);
        counter.put(num, cnt-1);
      }
    }
    int[] result = new int[list.size()];
    for (int i = 0; i < list.size(); ++i)
      result[i] = list.get(i);
    return result;
  }

  // Time: O(m*log(m)+n*log(n)), Space: O(k)
  public int[] intersectSort(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);

    int i = 0, j = 0, m = nums1.length, n = nums2.length;
    List<Integer> list = new ArrayList<>();
    while (i < m && j < n) {
      if (nums1[i] == nums2[j]) {
        list.add(nums1[i]);
        ++i; ++j;
      } else if (nums1[i] < nums2[j]) {
        ++i;
      } else ++j;
    }
    int[] result = new int[list.size()];
    for (int k = 0; k < list.size(); ++k)
      result[k] = list.get(k);
    return result;
  }

}