【LeetCode-27】移除元素

一、算法：移除元素问题

27. 移除元素 - 力扣（LeetCode）

二、题目描述

👋

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。

返回 k。

三、相关知识

数组

数组是最基础且常用的数据结构之一，它是一种线性数据结构，由一组 连续的内存空间 组成，用于存储相同类型的元素。

（1）数组的特点

随机访问：通过索引可以在 O(1) 时间内访问任意元素。例如，nums[3] 可以直接访问数组的第 4 个元素。

连续存储：数组的元素在内存中是连续存储的，这使得访问效率非常高。

固定大小：数组的大小在初始化时确定，无法动态调整（除非使用动态数组，如 Java 中的 ArrayList 或 Python 中的 list）。

内存效率高：由于元素连续存储，数组的访问和操作效率较高。

（2）数组的操作

访问元素：时间复杂度为 O(1)，例如 nums[i]。

插入元素：在数组中间或开头插入元素需要移动后续元素，时间复杂度为 O(n)。

删除元素：删除数组中间或开头的元素需要移动后续元素，时间复杂度为 O(n)。

查找元素：如果数组未排序，需要遍历查找，时间复杂度为 O(n)；如果数组已排序，可以使用二分查找，时间复杂度为 O(log n)。

（3）数组的优缺点

优点：

访问速度快，时间复杂度为 O(1)。

内存连续，适合存储大量数据。

缺点：

大小固定，无法动态扩展。

插入和删除操作效率低，时间复杂度为 O(n)。

时间复杂度与空间复杂度

（1）时间复杂度

时间复杂度用于描述算法运行时间随输入规模增长的趋势。它是算法效率的重要指标。

O(1)：常数时间复杂度。无论输入规模多大，算法的时间都是固定的。例如访问数组元素。

O(n)：线性时间复杂度。算法的运行时间与输入规模成线性关系。例如遍历数组。

（2）空间复杂度

空间复杂度用于描述算法所需的额外内存空间随输入规模增长的趋势。

O(1)：原地操作。算法的额外空间需求与输入规模无关。例如交换两个变量的值。

O(n)：算法的额外空间需求与输入规模成线性关系。例如复制一个数组。

O(n^2)：算法的额外空间需求与输入规模的平方成正比。例如生成一个二维数组。

（3）示例

遍历数组：

时间复杂度：O(n)，需要遍历所有元素。

空间复杂度：O(1)，只使用了常数级别的额外空间。

双重循环：

时间复杂度：O(n^2)，需要嵌套遍历所有元素。

空间复杂度：O(1)，通常不需要额外空间。

指针

指针是一种变量，用于存储另一个变量的内存地址。在算法中，指针常用于快速访问和操作数据。

（1）指针的基本概念

指针的作用：通过指针可以直接访问内存中的数据，避免频繁的数据复制。

指针的类型：指针的类型决定了它所指向的数据类型。例如，int* 是一个指向整数的指针。

指针的操作：

取地址：使用 & 符号获取变量的地址。例如 int* ptr = &num;。

解引用：使用 * 符号访问指针指向的值。例如 int val = *ptr;。

指针运算：指针可以进行加减运算，用于访问相邻的内存地址。

（2）指针在算法中的应用

双指针：

快慢指针：用于解决链表或数组中的问题，如判断链表是否有环、寻找链表的中间节点。

对撞指针：用于解决有序数组中的问题，如两数之和、三数之和。

滑动窗口：

通过两个指针维护一个窗口，用于解决子数组或子字符串问题，如最大子数组和、最小覆盖子串。

（3）指针的优势

高效访问：通过指针可以直接访问内存中的数据，避免数据复制。

节省空间：指针只需要存储地址，不需要存储数据本身。

灵活操作：指针可以动态调整，适合处理复杂的数据结构，如链表、树、图等。

四、解题方法

java%E5%AE%9E%E7%8E%B0" name="java%E5%AE%9E%E7%8E%B0">java实现

方法1：暴力解法

java">class Solution {
    public int removeElement(int[] nums, int val) {
        int length = nums.length; // 记录数组的原始长度
        for (int i = 0; i < length; i++) {
            if (nums[i] == val) { // 如果当前元素等于 val
                // 将后面的元素依次向前移动一位，覆盖掉当前元素
                for (int j = i + 1; j < length; j++) {
                    nums[j - 1] = nums[j];
                }
                length--; // 数组长度减 1
                i--; // 因为当前元素被覆盖，需要重新检查当前位置
            }
        }
        return length; // 返回新数组的长度
    }
}

方法2：双指针法

java">class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0; // 慢指针，用于记录新数组的位置
        for (int j = 0; j < nums.length; j++) { // 快指针 j 遍历整个数组
            if (nums[j] != val) { // 如果当前元素不等于 val
                nums[i] = nums[j]; // 将其复制到新数组的位置
                i++; // 慢指针向后移动
            }
        }
        return i; // 返回新数组的长度
    }
}

方法3：双指针优化（减少赋值操作）

java">class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0; // 慢指针，用于记录新数组的位置
        int n = nums.length; // 记录数组的原始长度
        while (i < n) { // 遍历数组
            if (nums[i] == val) { // 如果当前元素等于 val
                nums[i] = nums[n - 1]; // 将其与数组末尾的元素交换
                n--; // 数组长度减 1
            } else {
                i++; // 慢指针向后移动
            }
        }
        return n; // 返回新数组的长度
    }
}

javascript%E5%AE%9E%E7%8E%B0" name="javascript%E5%AE%9E%E7%8E%B0">javascript实现

方法1：暴力解法

javascript">function removeElement(nums, val) {
    let length = nums.length; // 记录数组的原始长度
    for (let i = 0; i < length; i++) {
        if (nums[i] === val) { // 如果当前元素等于 val
            // 将后面的元素依次向前移动一位，覆盖掉当前元素
            for (let j = i + 1; j < length; j++) {
                nums[j - 1] = nums[j];
            }
            length--; // 数组长度减 1
            i--; // 因为当前元素被覆盖，需要重新检查当前位置
        }
    }
    return length; // 返回新数组的长度
}

方法2：双指针法

javascript">function removeElement(nums, val) {
    let i = 0; // 慢指针，用于记录新数组的位置
    for (let j = 0; j < nums.length; j++) { // 快指针 j 遍历整个数组
        if (nums[j] !== val) { // 如果当前元素不等于 val
            nums[i] = nums[j]; // 将其复制到新数组的位置
            i++; // 慢指针向后移动
        }
    }
    return i; // 返回新数组的长度
}

方法3：双指针法优化（减少赋值操作）

javascript">function removeElement(nums, val) {
    let i = 0; // 慢指针，用于记录新数组的位置
    let n = nums.length; // 记录数组的原始长度
    while (i < n) { // 遍历数组
        if (nums[i] === val) { // 如果当前元素等于 val
            nums[i] = nums[n - 1]; // 将其与数组末尾的元素交换
            n--; // 数组长度减 1
        } else {
            i++; // 慢指针向后移动
        }
    }
    return n; // 返回新数组的长度
}

五、代码逻辑总结

暴力解法：

- 通过双重循环，每当发现等于 val 的元素时，将后面的元素向前移动覆盖。
- 时间复杂度为 O(n^2)，效率较低。

双指针法：

- 使用快指针 j 遍历数组，慢指针 i 记录新数组的位置。
- 当 nums[j] 不等于 val 时，将其复制到 nums[i]。
- 时间复杂度为 O(n)，效率较高。

双指针优化：

- 当 nums[i] 等于 val 时，将其与数组末尾的元素交换，并减少数组长度。
- 适用于被删除元素较少的场景，减少了赋值操作。

六、资料参考

27. 移除元素 - 力扣（LeetCode）
代码随想录