在计算机领域,算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始,跟随我每天刷一道算法题吧!


在此之前,我们刷的几乎都是有关数组操作的算法题。在接下来的几天里,我们将学习 “双指针技巧”,它可以帮助我们解决许多与数组相关的问题。

双指针专题 第三天。

LeetCode #27 移除元素

题目

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

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2

你不需要考虑数组中超出新长度后面的元素。

示例2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

解题思路

快慢双指针思路:

与 思路类似。使用两个指针,一个用于原始数组的迭代,另一个总是指向“新数组”的最后一个位置。将不需要移除的值放入“新数组”中。

这种思路只会处理不需要移除的值。所以当不需要移除的值比较多时,效率比较低。

快慢双指针代码:

public int removeElement(int[] nums, int val) {
int current = -1; // 慢指针
int index = 0; // 快指针
int length = nums.length;

for(; index < length; index++){、
// 把不等于 val 的值移到数组的前面
if(nums[i] != val){
nums[++current] = nums[i];
}
}
return current + 1;
}

左右双指针思路:

与快慢双指针相反,左右双指针只会处理需要移除的值。使用两个指针,一个用于原始数组的迭代,另一个总是指向数组的最后一个位置。将需要移除的值放入数组中的末尾。

所以当需要移除的值比较多时,效率比较低。

左右双指针代码:

public int removeElement(int[] nums, int val) {
int current = nums.length; // 右指针
int index = 0; // 左指针

while(index < current){
// 把等于 val 的值移到数组的后面
if(nums[index] == val){
nums[index] = nums[--current];
}else{
index++;
}
}

return current;
}

评论