卡码网--数组篇(移除元素)

系列文章目录

---

---

前言

代码随想录:详情链接

---

27. 移除元素

力扣27 https://leetcode.cn/problems/remove-element/description/

Step1: 读题:

1. 原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
2. 不要使用额外的数组空间，必须仅使用 O(1) 额外空间并原地修改输入数组。
3. 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素

Step2: 注意点:

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

Step3: 先用暴力法试试

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for (int i = 0; i < size; i++) {if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位for (int j = i + 1; j < size; j++) {nums[j - 1] = nums[j];}i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位size--; // 此时数组的大小-1}}return size;}
};

这里时间复杂度是O(n^2),空间复杂度是O(1)。具体思路就是循环所有元素，如果等于val，则后面的元素都向前移动一维覆盖该元素。然后数组长度会减一，循环i也要减1。

Python

class Solution:def removeElement(self, nums: List[int], val: int) -> int:size = len(nums)i = 0while(i<size):if(nums[i]==val):for j in range(i,size-1):nums[j]=nums[j+1]size =size -1else:i = i+1return size

Step 4 双指针法

其实我的理解就是慢指针指向的是新数组，快指针指向的是原数组，到时候直接返回慢指针指向的数组就可以得到结果。

C++

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();int fast = 0;int slow = 0;for (fast=0;fast<size;fast++)if(nums[fast]!=val)nums[slow++]=nums[fast];return slow;}
};

class Solution:def removeElement(self, nums: List[int], val: int) -> int:size = len(nums)fast = 0slow = 0while(fast<size):if nums[fast]!=val:nums[slow]=nums[fast]slow = slow +1fast = fast +1return slow

时间复杂度：O(n)，其中n是数组的长度。因为fast指针需要遍历整个数组一次。
空间复杂度：O(1)。因为只使用了常数个额外变量来存储指针和数组长度。

总结

26. 删除有序数组中的重复项

283. 移动零

844. 比较含退格的字符串

977. 有序数组的平方