算法练习——移除元素

2021年1月23日算法练习为27. 移除元素,这道题要求使用原地算法,并且我们需要将元素整理好,因此我们只需要找到需要移除的元素,并将不需要移除的元素替换到这个位置上即可。因此我们可以使用双指针法来解决,左指针负责找移除的元素,找到后将右指针的元素替换到左指针位置即可,直到两个指针擦肩而过说明所有的不需要移除的元素以及移动到了左指针的前面了,因此移除元素后的数组长度为左指针的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}
}

今天这道练习主要能够训练原地算法的思路,这道题的官方题解中有一个双指针是从头到尾遍历,非需要移除的元素就放到头指针指向的位置,这样就需要执行数组长度-需要移除元素个数次,而这里的解法则是只需要执行所需要移除元素个数次,在需要移除的元素少的情况下效率会比较高,与题解中的第二方法一致。