代码随想录训练营第一天 | 27.移除元素

27.移除元素

Question

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

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

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

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

• 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

如果所有的断言都通过，你的解决方案将会 通过。

示例 ：

Idea

解题思路

📖

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

暴力解法

这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。

删除过程如下：

• 时间复杂度：O(n^2)

• 空间复杂度：O(1)

指针法

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组

• 慢指针：指向更新 新数组下标的位置

删除过程如下：

• 时间复杂度：O(n)

• 空间复杂度：O(1)

Solution 1 快慢指针法(重要）

Solution 2 暴力解

Solution 3 相向双指针法（高效）

高效性的原因

1. 单次遍历：这个算法在最坏情况下也只需要遍历数组一次。虽然内部有两个循环，但它们分别处理左指针和右指针，整体上每个元素最多只会被处理一次。因此时间复杂度是 O(n)，其中 n 是数组的长度。

2. 双指针法：通过一个指针从左向右遍历（left 指针），另一个指针从右向左遍历（right 指针），可以同时检查和交换元素。这样做可以有效地减少不必要的操作和重复检查。

3. 原地操作：该算法不需要额外的空间来存储数组的副本，只在原数组上进行操作，空间复杂度是 O(1)。

总结

相关题目推荐