leetcode 27 移除元素-蒲公英云

leetcode 27 移除元素

前言

题目：27. 移除元素

参考答案：移除元素-力扣官方题解、移除元素-代码随想录

提交代码

题目限定：用vector来存储数据；不可以使用额外的空间。

所以：这道题目不能使用标记的方式(使用额外空间，标记需要删除元素的下标)解决；由于是顺序存储，直接删除的复杂度过高；题目给出的提示是，将需要删除的内容交换到数组后面(这是题目的思路)；

我使用“前后指针”实现上面的思路；答案使用“快慢指针”实现上面的思路。

前后指针的优缺点：交换的内容少；改变了原有的序列；交换完毕之后需顺序遍历一遍，以找到分界位置。时间复杂度为 2 ∗ O ( n ) 2*O(n) 2∗O(n)。

快慢指针的优缺点：不改变了原有的序列；交换完毕之后，慢指针指向的位置即为分界位置；交换的内容多；时间复杂度为 O ( n ) O(n) O(n)。

总的来说，我更倾向于快慢指针。

左右指针实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left=0, right=nums.size()-1; 
        while(left<right){
            while((nums[left]!=val) && (left<right)) // 从前向后找第一个val位置
                left++;
            while((nums[right]==val) && (left<right)) // 从后向前找第一个非val位置
                right--;
            // if(left<right)
            //     swap(nums[left],nums[right]);
            swap(nums[left],nums[right]); // 只有最后一次，自己和自己(不影响)，避免每次检查
            left++;
            right--;
        }
        int i=nums.size()-1;
        for(; i>=0; i--)
            if(nums[i]!=val)
                return i+1; // 前面非val长度
        return 0;
    }
};
int main(void){
    vector<int> nums = {3,2,2,3}; int val = 3;
    Solution s;
    int len = s.removeElement(nums,val);
    cout<<len<<endl;
    for(int i=0; i<len; i++)
        cout<<nums[i]<<" ";
    return 0;
}

快慢指针实现

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex=0,fastIndex=0;
        int len = nums.size();
        /// 没有要处理内容的时候，快慢指针一起向前走。
        /// 遇到需要处理内容的时候，慢指针留下标记，快指针继续向前走。
        /// 本题为例，使用[slowIndex,fastIndex)标记可以被填充的区域。[0,slowIndex)为非val列表
        for(; fastIndex<len; fastIndex++){
            if(nums[fastIndex]!=val){  
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
};