350.两个数组的交集II

链接：350.两个数组的交集II
难度：Easy
标签：数组、哈希表、双指针、二分查找、排序
简介：给定两个数组，编写一个函数来计算它们的交集。

题解 1 - typescript

• 编辑时间：2020-07-13
• 执行用时：76ms
• 内存消耗：37.1MB
• 编程语言：typescript
• 解法介绍：利用 map 来储存 num 和显示次数。

function intersect(nums1: number[], nums2: number[]): number[] {
  const map = new Map();
  const ans: number[] = [];
  for (const num of nums1) {
    const c = map.get(num);
    map.set(num, 1 + (c ? c : 0));
  }
  for (const num of nums2) {
    const c = map.get(num);
    if (c) {
      ans.push(num);
      map.set(num, c - 1);
    }
  }
  return ans;
}

题解 2 - c

• 编辑时间：2021-11-30
• 执行用时：8ms
• 内存消耗：6.2MB
• 编程语言：c
• 解法介绍：二分查找。

int comp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    qsort(nums2, nums2Size, sizeof(int), comp);
    qsort(nums1, nums1Size, sizeof(int), comp);
    int i1 = 0, i2 = 0, *ans = (int *)malloc(sizeof(int) * nums1Size);
    *returnSize = 0;
    while (i1 < nums1Size && i2 < nums2Size) {
        if (nums1[i1] == nums2[i2]) {
            ans[(*returnSize)++] = nums1[i1];
            i1++;
            i2++;
            continue ;
        } else if (nums1[i1] > nums2[i2]) {
            i2++;
        } else {
            i1++;
        }
    }
    return ans;
}