灯的个人博客

forever young,forever weeping.

0%

初级算法-找出重复的数字

发表于 更新于 分类于

题目

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

1
2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

说明：

  • 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。

  • 我们可以不考虑输出结果的顺序。
    进阶：

  • 如果给定的数组已经排好序呢？你将如何优化你的算法？

  • 如果 nums1 的大小比 nums2 小很多，哪种方法更优？

  • 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

题解

直觉版

1
2
3
4
5
6
7
8
9
10
11
12
13
function intersect(nums1: number[], nums2: number[]): number[] {
  if (nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1];
  }
  return nums1.filter((item) => {
    let index = nums2.findIndex((cItem) => item === cItem);
    if (index === -1) {
      return false;
    }
    nums2.splice(index, 1);
    return true;
  });
}

双指针版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function intersect(nums1: number[], nums2: number[]): number[] {
  nums1 = nums1.sort((a, b) => a - b);
  nums2 = nums2.sort((a, b) => a - b);
  let rightIndex = 0;
  let leftIndex = 0;
  let result = [];
  while (leftIndex < nums1.length && rightIndex < nums2.length) {
    if (nums1[leftIndex] === nums2[rightIndex]) {
      result.push(nums1[leftIndex]);
      leftIndex++;
      rightIndex++;
      continue;
    } else if (nums2[rightIndex] > nums1[leftIndex]) {
      leftIndex++;
      continue;
    } else {
      rightIndex++;
    }
  }
  return result;
}

参考