上海哪里网站备案,node.js做的网站,母婴网站建设,做网站主机要求LeetCode 27 - 移除元素#xff08;Remove Element#xff09;是一个简单但经典的双指针问题#xff0c;主要考察数组操作的基本功。虽然问题容易#xff0c;但掌握多种解法以及衍生的变体问题对解决更复杂的操作数组问题有帮助。 题目描述
输入#xff1a;整数数组 nums…LeetCode 27 - 移除元素Remove Element是一个简单但经典的双指针问题主要考察数组操作的基本功。虽然问题容易但掌握多种解法以及衍生的变体问题对解决更复杂的操作数组问题有帮助。 题目描述
输入整数数组 nums 和目标值 val。要求原地移除数组中所有等于 val 的元素并返回移除后数组的长度。注意 数组的元素可以被改变但空间复杂度要求 O(1)。函数返回不等于 val 的元素的长度最终结果的前部分元素排列无所谓。
示例
输入nums [3, 2, 2, 3], val 3
输出2 移除后的数组变为 [2, 2]输入nums [0,1,2,2,3,0,4,2], val 2
输出5 移除后的数组变为 [0, 1, 3, 0, 4]常用解法及模板
解法 1双指针法快慢指针
核心思想用两个指针 slow 和 fastfast 遍历数组所有元素slow 记录结果数组的索引。 如果 nums[fast] ! val将 nums[fast] 写到 nums[slow] 位置slow 自增。如果 nums[fast] val跳过不用写入。 遍历结束后nums[0..slow-1] 是保留的非 val 元素。
模板代码
class Solution {public int removeElement(int[] nums, int val) {int slow 0;for (int fast 0; fast nums.length; fast) {if (nums[fast] ! val) {nums[slow] nums[fast]; // 写入非目标值slow; // 慢指针前进}}return slow; // 最终的数组长度}
}复杂度分析
时间复杂度: O(n)遍历数组一次。空间复杂度: O(1)原地完成。 解法 2双指针法交换法
适用场景 如果题目不要求保留数组的顺序可以使用此解法。每次找到 val 时将其与数组最后一个元素交换从而用较少的操作移除目标值。 核心思想 使用双指针 left从头开始和 right从尾开始。如果 nums[left] val将其与 nums[right] 交换并递减 right。如果 nums[left] ! val继续前进。遍历结束时left 即为最终的结果长度。
模板代码
class Solution {public int removeElement(int[] nums, int val) {int left 0, right nums.length - 1;while (left right) {if (nums[left] val) {nums[left] nums[right];right--;} else {left;}}return left; // 最终长度}
}复杂度分析
时间复杂度: O(n)每个元素最多遍历一次。空间复杂度: O(1)原地操作。 解法 3计数后重写
核心思想先统计不等于目标值的所有索引再将这些索引的值逐个复制回数组。步骤 遍历数组统计有多少个非 val 的元素。通过线性遍历将非 val 的值重写到数组的前段。 局限性操作次数比双指针多空间申请多一小部分仍可 AC。
模板代码
class Solution {public int removeElement(int[] nums, int val) {int index 0;// 第一遍数非目标值for (int i 0; i nums.length; i) {if (nums[i] ! val) {nums[index] nums[i];}}return index; // 非目标值个数即数组长度}
}复杂度分析
时间复杂度: O(n)两次线性遍历统计 重写。空间复杂度: O(1)依旧是原地操作。 解法 4链表解法当输入为链表时
如果输入是链表而不是数组移除目标值时可以使用“指针删除”无需双指针。
核心思路 遍历链表跳过所有等于 val 的节点通过调整前驱节点的 next 跳过符合条件的节点。引入一个哑节点简化边界情况的处理。
模板代码
class Solution {public ListNode removeElements(ListNode head, int val) {ListNode dummy new ListNode(0, head);ListNode prev dummy, cur head;while (cur ! null) {if (cur.val val) {prev.next cur.next; // 删除当前节点} else {prev cur; // 前驱节点前移}cur cur.next; // 当前节点前移}return dummy.next;}
}复杂度分析
时间复杂度: O(n)遍历链表一次。空间复杂度: O(1)只调整指针顺序。 经典变体问题
变体 1移除所有值小于 val 的元素
在数组中移除所有小于指定值 val 的元素保留其他元素。
思路
双指针法快慢指针根据条件修改数组。
模板代码
class Solution {public int removeLessThan(int[] nums, int val) {int slow 0;for (int fast 0; fast nums.length; fast) {if (nums[fast] val) {nums[slow] nums[fast]; // 保留大于等于 val 的元素}}return slow;}
}变体 2移除重复元素
移除数组中重复的元素例如将 [1,1,2,2,3] 变为 [1,2,3]。
思路
快慢指针法slow 指针记录结果数组fast 用于遍历。在重复元素时跳过。
class Solution {public int removeDuplicates(int[] nums) {if (nums.length 0) return 0;int slow 0;for (int fast 1; fast nums.length; fast) {if (nums[fast] ! nums[slow]) {slow;nums[slow] nums[fast];}}return slow 1; // 新长度}
}变体 3移除 K 个范围内的元素
移除数组中值在 [low, high] 范围内的元素。
思路
改造 removeElement在条件中加入区间判断即可。
模板代码
class Solution {public int removeElementInRange(int[] nums, int low, int high) {int slow 0;for (int fast 0; fast nums.length; fast) {if (nums[fast] low || nums[fast] high) {nums[slow] nums[fast];}}return slow;}
}快速 AC 总结
首先掌握核心解法双指针法快慢指针。熟练理解变体换条件小于值、重复元素、区间范围时仍然可以用解法模板。对应场景数组 vs 链表选择合适实现。例如链表用修改指针操作更方便。高效背模板模板结构固定快速套用并扩展到变体问题。
