leetcode 27 移除元素

客官°小女子只卖身不卖艺 2022-09-07 05:00 212阅读 0赞

## 前言 ##

题目：[27. 移除元素][27.]

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

--------------------

## 提交代码 ##

题目限定：用`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;
        }
    };

[27.]: https://leetcode-cn.com/problems/remove-element/
[-]: https://leetcode-cn.com/problems/remove-element/solution/yi-chu-yuan-su-by-leetcode-solution-svxi/
[- 1]: https://leetcode-cn.com/problems/remove-element/solution/27-yi-chu-yuan-su-bao-li-jie-fa-shuang-zhi-zhen-ji/