三亩地 三亩地SAN MU DI · CODE DIARY
ARTICLE DETAIL

日记详情

真实记录编程学习的某一天,欢迎挑你感兴趣的翻一翻。

02、双指针删除元素

02、双指针删除元素

一、快慢指针


   双指针其实原本就是一起移动的,当遇到了需要删除的元素的时候就发生的变化,此时呢,慢指针就会停下来,完成数据的覆盖,而快指针继续移动

这样做的好处就是可以将原本是O(n^2)的时间复杂度的方法,变为O(n)的时间复杂度。数组删除元素本质上是覆盖原本的元素,并不是真正的删除,而后面覆盖的元素

是不会消失的,只会保留。

源代码:


class Solution {
public:int removeElement(vector<int>& nums, int val) {int slow = 0;for (int fast = 0 ; fast < nums.size() ; fast ++ ){if (nums[fast] != val){nums[slow] = nums[fast];   slow ++;}}return slow;}
};

注意:
(1) 在进行双指针的时候,循环语句中的nums[slow] = nums[fast] 其实就是将数组中的元素更新;

   (2) 看似没有删除元素的操作,其实是在判断的时候如果发现了需要删除的元素,就是暂停slow的移动,也就是暂停了for循环;

   (3) 当不是删除的元素的时候,此时的fast(快指针)已经在slow(慢指针)前面了,然后再更新复制,便完成了删除操作;


二、暴力破解

   使用两成for循环,将元素逐个拆解, 知道全部都弄完;这样的空间复杂度是O(1),但是时间复杂度变成了O(n),所以这样的作法不太优化;

源代码:


class Solution {
public:int removeElement(vector<int>& nums, int val) {int num = nums.size();   // 此处可以不用将 nums.size() - 1; 题目中要求的是返回数组的长度;for (int i = 0 ; i < num ; i++){   // 当然这个地方也可以用 i <= num - 1 来实现,本质都是为了不让数组的下标越界;if (nums[i] == val){for (int j = i + 1 ; j < num; j ++){nums[j - 1] = nums[j];}i --;  // 为啥要减一呢 ?因为i 后面的元素都往前面移动了 num --;  // 找到了要删除的元素就 “删除” ,将元素覆盖掉}}return num;}
};

注意:
(1) 暴力破解的内层循环其实是在找到需要删除的元素的时候,将该元素的后面的所有元素往前面移动所以才是 nums[j -1] = num[j];

← 返回列表