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)

参数：

mergeTwoSortedArrayV2() ​

描述：

88.合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

逆向双指针解法

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

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

  • 时间复杂度 O(m + n)

  • 空间复杂度 O(1)

参数：

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)。我们只需要常数的空间保存若干变量

参数：

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 循环判断指针对撞时退出循环

参数：