T Comm

Appearance

引入 ​

ts
import {
  mergeTwoSortedArrayV1,
  mergeTwoSortedArrayV2,
  removeElementInArrayV1,
  removeElementInArrayV2
} from 't-comm';

// 不支持 tree-shaking 的项目
import {
  mergeTwoSortedArrayV1,
  mergeTwoSortedArrayV2,
  removeElementInArrayV1,
  removeElementInArrayV2
} from 't-comm/lib/algorithm/index';

// 只支持 ESM 的项目
import {
  mergeTwoSortedArrayV1,
  mergeTwoSortedArrayV2,
  removeElementInArrayV1,
  removeElementInArrayV2
} from 't-comm/es/algorithm/index';

mergeTwoSortedArrayV1() ​

描述：88.合并两个有序数组 https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150 双指针解法

将两个数组看成队列，每次从数组头部取出较小数字放到结果中

时间复杂度 O(m + n)

空间复杂度 O(m + n)

参数：

示例

ts
const nums1 = [1, 3, 9, 0, 0, 0, 0];
const nums2 = [2, 4, 5, 9];
mergeTwoSortedArrayV1(nums1, nums2, 3, 4);
// [1, 2, 3, 4, 5, 9, 9]

const a = [1, 2, 3, 0, 0, 0];
const b = [2, 5, 6];
mergeTwoSortedArrayV1(a, b, 3, 3);
// [1, 2, 2, 3, 5, 6]

mergeTwoSortedArrayV2() ​

描述：88.合并两个有序数组 https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150 逆向双指针解法

指针初始位置在尾部，每次向前移动

不用临时数组 temp，因为不用担心前面的被覆盖

时间复杂度 O(m + n)

空间复杂度 O(1)

参数：

示例

ts
const nums1 = [1, 3, 9, 0, 0, 0, 0];
const nums2 = [2, 4, 5, 9];
mergeTwoSortedArrayV2(nums1, nums2, 3, 4);
// [1, 2, 3, 4, 5, 9, 9]

const a = [1, 2, 3, 0, 0, 0];
const b = [2, 5, 6];
mergeTwoSortedArrayV2(a, b, 3, 3);
// [1, 2, 2, 3, 5, 6]

removeElementInArrayV1() ​

描述：27.移除元素 https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150 双指针。

右指针 right 指向当前将要处理的元素，左指针 left 指向下一个将要赋值的位置。

如果右指针不等于 val，就将右指针指向的值赋值给左指针位置，左指针右移一位。

时间复杂度：O(n)，其中 n 为序列的长度。我们只需要遍历该序列至多两次。

空间复杂度：O(1)。我们只需要常数的空间保存若干变量

参数：

示例

ts
removeElementInArrayV1([3, 2, 2, 3], 3); // 2
removeElementInArrayV1([0, 1, 2, 2, 3, 0, 4, 2], 2); // 5

removeElementInArrayV2() ​

描述：27.移除元素 https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150 对撞指针。

两个指针初始时分别位于数组的首尾，向中间移动遍历该序列。

如果左指针 left 指向的元素等于 val，此时将右指针 right 指向的元素复制到左指针 left 的位置，然后右指针 right 左移一位。否则左指针 left 右移一位。

时间复杂度：O(n)，其中 n 为序列的长度。我们只需要遍历该序列至多一次。

空间复杂度：O(1)。我们只需要常数的空间保存若干变量

第一种是快慢指针，第二种是对撞指针，同样是双指针，前者同向出发，因此用一个 for 循环实现遍历；后者前后出发，因此用 while 循环判断指针对撞时退出循环

参数：

示例

ts
removeElementInArrayV2([3, 2, 2, 3], 3); // 2
removeElementInArrayV2([0, 1, 2, 2, 3, 0, 4, 2], 2); // 5