题目描述:
给你一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例:
输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
解题1:暴力循环
两层 for 循环,一个 for 循环遍历数组元素 ,第二个 for 循环更新数组。时间复杂度 O(n^2),空间复杂度 O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public static int removeElement(int[] nums, int val) { int size = nums.length; for (int i = 0; i < size; i++) { if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位 for (int j = i + 1; j < size; j++) { nums[j - 1] = nums[j]; } // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位 i--; // 此时数组的大小-1 size--; } } return size; }
需要注意的是,数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。所以我们需要将待删除元素之后的元素全部前移一位。
解题2:快慢指针法
通过一个快指针和慢指针在一个 for 循环下完成两个 for 循环的工作。时间复杂度 O(n),空间复杂度 O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13public static int removeElement2(int[] nums, int val) { // 快指针 int i = 0; // 慢指针 int j = 0; for (j = 0; i < nums.length; i++) { if (nums[i] != val) { nums[j] = nums[i]; j++; } } return j; }
双指针法(快慢指针法)在数组和链表的操作中是非常常见的,很多考察数组、链表、字符串等操作的面试题,都使用双指针法。
最后
以上就是甜美小土豆最近收集整理的关于leetCode-27: 移除元素的全部内容,更多相关leetCode-27:内容请搜索靠谱客的其他文章。
发表评论 取消回复