349.两个数组的交集

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

题解 1 - javascript

• 编辑时间：2020-02-28
• 执行用时：104ms
• 内存消耗：34.9MB
• 编程语言：javascript
• 解法介绍：使用 Set 对象去重后再遍历。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  const set1 = new Set(nums1);
  const set2 = new Set(nums2);
  const result = [];
  for (const num of set2) {
    if (set1.has(num)) {
      result.push(num);
    }
  }
  return result;
};

题解 2 - javascript

• 编辑时间：2020-02-28
• 执行用时：48ms
• 内存消耗：34.8MB
• 编程语言：javascript
• 解法介绍：使用 Set 对象去重后用 filter 遍历。

var intersection = function (nums1, nums2) {
  const a = new Set(nums1);
  const b = new Set(nums2);
  return [...new Set([...a].filter(x => b.has(x)))];
};

题解 3 - c

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

int comp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}
int bs(int *nums, int n, int num) {
    int l = 0, r = n - 1, m;
    if (nums[l] > num || nums[r] < num) return 0;
    while (l < r) {
        m = (l + r) >> 1;
        if (nums[m] == num) return 1;
        if (nums[m] > num) r = m - 1;
        else l = m + 1;
    }
    return nums[l] == num ? 1 : 0;
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    qsort(nums2, nums2Size, sizeof(int), comp);
    qsort(nums1, nums1Size, sizeof(int), comp);
    int *ans = (int *)malloc(sizeof(int) * (nums1Size + nums2Size));
    *returnSize = 0;
    for (int i = 0; i < nums1Size; i++) {
        if (i < nums1Size - 1 && nums1[i] == nums1[i + 1]) continue;
        int num = nums1[i];
        int check = bs(nums2, nums2Size, num);
        if (check) ans[(*returnSize)++] = num;
    }
    return ans;
}

题解 4 - typescript

• 编辑时间：2020-11-02
• 执行用时：96ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：利用 set 去重搜索。

function intersection(nums1: number[], nums2: number[]): number[] {
  const set = new Set(nums1);
  const arr: number[] = [];
  for (const num of nums2) {
    set.has(num) && arr.push(num);
  }
  return [...new Set(arr)];
}