力扣面试经典算法150题：移除元素

移除元素

今日的题目依旧是力扣面试经典算法150题中数组相关的题目：移除元素

题目链接：https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150

题目描述

给定一个排序数组 nums 和一个值 val，需要在原地移除数组中所有等于val 的元素，并返回移除后数组的新长度。不需要考虑超出新长度以外的元素。

• 注意:
  • 必须在原地修改输入数组，不能使用额外的数组空间。
  • 元素的顺序可以改变，你不需要考虑数组中超出新长度后面的元素。
• 示例:
  • 输入:
    nums = [3,2,2,3], val = 3
  • 输出:
    新长度为 2，数组变为 [2,2]（注意：返回值为新长度，数组内容可以不是连续的）
• 解释:
  • 数组 nums 中的值 3 被移除了两次。
  • 移除后的新数组长度为 2，数组内容为 [2,2]。

题目分析

题目要求我们在不使用额外空间的情况下，移除数组中的特定元素，并返回移除后的数组长度。

为了达到 O(1) 的额外空间复杂度，这要求我们需要在原地修改数组。

解题思路

题目的要求就两个，一个移出元素，一个将不同的元素放到原本的数组中。这就意味着我们需要在一个循环中进行两种操作，这里很容易就会想到用双指针来完成，一个指针拿出元素比较，一个指针将元素放入数组，并且这个指针最后停留的下标就是最后一个不同的元素。

实际算法代码

根据以上分析和思路，我们可以写出以下代码：

import java.util.Arrays;

/**
 * description
 *
 * @author 明月望秋思
 * @date 2024/8/6 
 */
public class RemoveElement {
    /**
     * 移除数组中的指定元素
     *
     * @param nums 输入数组
     * @param val  需要移除的值
     * @return 移除后的新数组长度
     */
   public int removeElement(int[] nums, int val) {
        // 指针1,用于遍历数组比较元素
        int i = 0;
        // 指针2,用于记录新数组的下标位置
        int j = 0;

        // 遍历数组
        while (i < nums.length) {
            // 比较元素是否与val相等
            if (nums[i] != val) {
                nums[j] = nums[i];
                // 只有元素不同时，才放入元素并更新指针2
                j++; 
            }
            // 更新指针1，不管元素是否相同，都要向下遍历
            i++; 
        }
		// 返回新数组的长度,因为在循环中进行了++的操作
        return j; 
    

    public static void main(String[] args) {
        RemoveElement solution = new RemoveElement();

        // 示例数据
        int[] nums = {3, 2, 2, 3};
        int val = 3;

        // 调用移除方法
        int newLength = solution.removeElement(nums, val);

        // 输出新长度和移除后的数组
        System.out.println("New length: " + newLength);
        System.out.println("Modified array: " + Arrays.toString(Arrays.copyOfRange(nums, 0, newLength)));
    }
}

提交代码，测试通过。

因为算法用到了双指针，下面讲一下双指针法的内容。

双指针法

双指针法是一种常用的算法技巧，它通过使用两个指针来遍历数据结构（如数组或链表），以简化问题的解决过程。

使用场景

双指针法适用于多种场景，下面列举了一些常见的使用双指针法的场景及其原因：

• 在原数组对象操作数组
  • 场景描述：不增加额外空间复杂度度的情况下完成对数组的操作。
  • 原因：双指针法可以直接在原数组上进行操作，可以减少不必要的比较和浪费额外的空间。
• 寻找两个数使它们的和为特定值
  • 场景描述：给定一个有序数组，找到数组中两个数，使它们的和等于特定的目标值。
  • 原因：有序数组允许我们使用双指针从两端向中间逼近，一个指针从头部开始，另一个从尾部开始。这样可以避免不必要的比较，提高效率。
• 快速排序中的分区操作
  • 场景描述：在快速排序算法中，需要选择一个基准值，并将小于基准值的元素放在左边，大于基准值的元素放在右边。
  • 原因：双指针可以帮助我们有效地进行分区操作，一个指针从左向右移动，另一个从右向左移动，当两个指针指向的元素不符合分区规则时，交换它们的位置。
• 求解回文子串
  • 场景描述：给定一个字符串，判断它是否是回文串，或者找出最长的回文子串。
  • 原因：对于回文串，中心对称的特性使得我们可以使用双指针从中心向两边扩展来检查字符串是否为回文。
• 求解链表的中间节点
  • 场景描述：给定一个单链表，需要找到链表的中间节点。
  • 原因：使用快慢指针，快指针每次移动两步，慢指针每次移动一步，当快指针到达链表尾部时，慢指针正好位于中间。
• 反转链表
  • 场景描述：给定一个链表，需要反转链表的顺序。
  • 原因：使用双指针技巧，一个指针指向当前节点，另一个指针指向当前节点的前一个节点，通过调整指针方向来实现反转。
• 滑动窗口
  • 场景描述：在数组或字符串中找到满足特定条件的最大或最小子序列。
  • 原因：双指针可以用来定义滑动窗口的边界，一个指针作为窗口的起始位置，另一个指针作为窗口的结束位置，随着遍历，动态调整窗口大小以满足条件。
• 寻找重复元素
  • 场景描述：在有序数组中查找重复元素。
  • 原因：使用双指针技巧，一个指针从头开始，另一个指针从尾开始，根据元素的大小关系移动指针来寻找重复项。
• 合并两个有序数组
  • 场景描述：给定两个有序数组，需要将它们合并成一个新的有序数组。
  • 原因：使用双指针从后向前比较两个数组的元素，并将较大的元素放入结果数组的末尾，可以保证合并后的数组仍然是有序的。
• 检测链表中的环
  • 场景描述：给定一个链表，需要检测链表中是否存在环。
  • 原因：使用快慢指针技巧，快指针每次移动两步，慢指针每次移动一步，如果存在环，快指针最终会追上慢指针。

双指针法之所以在这些场景中有效，是因为它能够减少不必要的比较次数，提高算法的时间效率，并且在很多情况下能够避免使用额外的空间，从而达到 O(1) 的空间复杂度。

双指针法的优点：

双指针法有以下优点：

• 原地修改：不需要额外的空间来存储新数组，直接在原数组上进行修改，这样就可以在 O(1) 的额外空间复杂度下完成移除操作。
• 保持有序性：在移除元素的过程中，可以使有效元素仍然保持有序。
• 效率高：只需要遍历一次数组即可完成移除操作，时间复杂度为 O(n)。
• 简单易实现：双指针法的逻辑简单，易于理解和实现

总结

实际上上一篇文章中的题目，也是用的双指针法。

双指针法在处理数组的算法题时，是比较常见且又好用的一种解决办法。

熟练使用可以更好的帮助在数组方面的问题！