leetcode-27.移除元素 | 双指针与数组操作详解

最新推荐文章于 2025-03-06 16:54:26 发布

Einstein777

最新推荐文章于 2025-03-06 16:54:26 发布

阅读量378

点赞数 5

分类专栏：数据结构文章标签： leetcode 算法 c++

本文链接：https://blog.csdn.net/Cpythonjavamacos/article/details/144513529

版权

数据结构专栏收录该内容

5 篇文章

订阅专栏

在这篇博客中，我们将深入解析 27. 移除元素 问题，并提供两种高效的解决方法，分别是 暴力移除法 和 双指针法。

题目描述

给定一个数组 nums 和一个值 val，你需要就地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

要求：

不需要为其他元素分配额外的空间。
数组的元素顺序可以改变，最终结果由前 k 个元素组成，其中 k 是新数组的长度。

示例

输入：nums = [3,2,2,3], val = 3  
输出：2, nums = [2,2,_]  
解释：函数应该返回新的长度 2，同时数组前两个元素均为 2。你不需要考虑数组中超出新长度部分的内容。

解法一：暴力移除法

思路

遍历数组，遇到需要移除的元素时，将该位置后的元素向前移动一位。
每次移除一个元素时，数组长度减 1。
注意遍历时，由于数组被压缩，当前索引可能需要调整。

代码实现

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int length = nums.size();
        for (int i = 0; i < length; i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < length; j++) {
                    nums[j - 1] = nums[j];
                }
                length -= 1;
                i -= 1; // 调整索引，防止跳过元素
            }
        }
        return length;
    }
};

复杂度分析

时间复杂度：O(n²)。在最坏情况下，每次移除元素都会导致后续元素整体前移。
空间复杂度：O(1)。没有使用额外的存储空间。

优缺点

优点：代码逻辑简单，便于理解。
缺点：对于长数组性能较差，因为频繁的整体移动会增加时间开销。

解法二：双指针法

思路

使用两个指针：
- 快指针 (i)：用于遍历数组的每个元素。
- 慢指针 (slow_index)：指向结果数组的最后一个位置。
遍历数组时，将非目标值的元素覆盖到慢指针所指的位置。
遍历完成后，慢指针的值即为新数组的长度。

代码实现

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

优化版（交换法）

为了减少多余的赋值操作，可以在条件满足时直接交换元素位置：

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