「力扣」第 27 题:移动元素
传送门:英文网址:27. Remove Element ,中文网址: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。 注意这五个元素可为任意顺序。 你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝 int len = removeElement(nums, val); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }
思路:设置一个指针 j
,遍历过程中遇到要删除的元素,跳到下一个,遇到保留元素,j
位置赋值,并且 j
索引 + 1
,最后不要忘记遍历完成以后,删除索引 j
后面的所有元素。
Python 代码:
class Solution:
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
size = len(nums)
if size == 0:
return 0
j = 0
for i in range(size):
if nums[i] != val:
nums[j] = nums[i]
j += 1
return j
「力扣」第 27 题:删除元素
要求:在一个数组里面移除指定元素,并返回新的数组的长度。
public class Solution {
public int removeElement(int[] nums, int val) {
int i = 0;
int j = 0;
for (; i < nums.length; i++) {
if(nums[i]==val){
continue;
}
nums[j] = nums[i];
// 只要遇到与 val 不等的元素,就累加 1
// 所以,直接返回 j 就可以了
j++;
}
return j;
}
public static void main(String[] args) {
Solution solution = new Solution();
int result = solution.removeElement(new int[]{3,2,2,3},2);
System.out.println(result);
}
}
分析:就这道问题,我们要考虑的问题是:
- 如何定义删除?从数组中删除?还是放在数组的末尾?
- 剩余元素的排列是否要保证原来的相对顺序?
- 是否有空间复杂度的要求?
我的解答:有瑕疵,因为在 Java 中数组的长度是固定的。在这个函数中不能移除 Java 数组中的元素。但是居然在 LeetCode 中通过了。
public class Solution {
// Given input array nums = [3,2,2,3], val = 3
/**
* 题目的要求中说,顺序可以改变
* 不管怎么样,先写出来最要紧
* 难点:Java 中的数组元素怎么删除,这里我没有实现
*
* @param nums
* @param val
* @return
*/
public int removeElement(int[] nums, int val) {
int k = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[k++] = nums[i];
}
}
return k;
}
public static void main(String[] args) {
int[] nums = {3, 2, 2, 3};
int val = 3;
Solution solution = new Solution();
int removeElementNum = solution.removeElement(nums, val);
System.out.println(removeElementNum);
System.out.println(Arrays.toString(nums));
}
}
第 2 遍解答,其实本质上是一样的,思路分析:对题目的说明:在一个数组里面移除指定元素,并返回新的数组的长度。
解题思路:给出两个指针 i 和 j,其中 i 就想我们平常遍历数组元素一样,是一个普通的循环遍历。
和 j 就像是一支笔,我们要借助这支笔,往一个新数组里面写数据。
只不过,根据题意,我们恰恰好可以利用原来的数组的空间,这是因为,我们的任务是 Remove Element,新数组的元素个数一定不会超过原数组的元素个数。
Java 代码:
public class Solution {
public int removeElement(int[] nums, int val) {
int i = 0;
int j = 0;
for (; i < nums.length; i++) {
if(nums[i]==val){
continue;
}
nums[j] = nums[i];
// 只要遇到与 val 不等的元素,就累加 1
// 所以,直接返回 j 就可以了
j++;
}
return j;
}
public static void main(String[] args) {
Solution solution = new Solution();
int result = solution.removeElement(new int[]{3,2,2,3},2);
System.out.println(result);
}
}
(本节完)