LeetCode笔记

数组

数组删除元素

在原数组中删除中某一元素,并返回最终数组的长度(忽略新长度后面的元素)

解法一:

可使用快指针(用于遍历原数组)和慢指针(当前在原数组中填入元素的位置)来实现

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

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

解法二:(优化)

使用双指针,两个指针初始时分别位于数组的首尾,向中间移动遍历该序列。避免了需要保留的元素的重复赋值操作。

对于有序数组应想到二分查找,时间复杂度为 O(log n)