跳转至

27 移除元素

leetcode 链接

本题重点:数组删除第i个元素的方法:将i之后的元素依次左移1位

暴力做法

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for(int i = 0; i < size; i++){
            // 找到数值等于val的元素
            if(val == nums[i]){
                // 数组删除第i个元素的方法:将i之后的元素依次左移1位
                for(int j = i + 1; j < size; j++){
                    nums[j - 1] = nums[j];
                }
                // 删除第i个元素,第i个元素变成新元素,下一次依然从i开始遍历
                i--;
                // 删除元素后,数组大小减1
                size--;
            }
        }
        // 数组剩余的都是不等于val的元素
        // 因此返回数组大小即可
        return size;
    }
};

时间复杂度:\(O(n^2)\)

空间复杂度:\(O(1)\)

双指针法

和数组去重思路几乎一样

注意分辨题意和slowIndex初始化的含义,这决定了slowIndex++放在nums[slowIndex] = nums[fastIndex]之前还是之后

在本题中,需要删除等于val的元素, 如果slowIndex = 0,说明我们默认第一个元素不等于val,这就需要

nums[slowIndex] = nums[fastIndex];
slowIndex++;

如果slowIndex = -1,说明我们默认第一个元素不确定是否等于val,接下来我们需要维护第一个元素使其不等于val,那么需要

slowIndex++;
nums[slowIndex] = nums[fastIndex];
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 慢指针指向新数组末尾元素的下一个位置(插入的位置)
        // 新数组元素:数值不等于val的元素
        int slowIndex = 0;
        // 快指针指向从左到右数值不等于val的第一个元素
        for(int fastIndex = 0; fastIndex < nums.size(); fastIndex++){
            if(val != nums[fastIndex]){
                // 如果fastIndex指向的元素不等于val,需要将其加入到新数组中
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        // 慢指针指向新数组末尾元素的下一个位置
        // 因为元素索引从0开始,所以slowIndex就是元素个数
        return slowIndex;
    }
};

时间复杂度:\(O(n)\)

  • 只遍历了一次数组

空间复杂度:\(O(1)\)