导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-27.Remove Element

题目

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

翻译

给出一个数组和一个值,原地移除所有该值的实例并返回新的长度。
元素的顺序可以被打乱。新数组中,新的长度后的元素状态可以不必关心。

开始没理解题意,以为是计算除去给定值的元素的所有元素个数即可,还想怎么这么简单……

1
2
3
4
5
6
7
8
9
public class Solution {
public int removeElement(int[] nums, int val) {
int len = nums.length;
for (int num : nums)
if (num == val)
len--;
return len;
}
}

报错:

1
2
3
Input:[4,5], 4
Output:[4]
Expected:[5]

才明白了题意,是要把所有的非给定值的元素都移动到前面,再返回新的长度,而其他元素的值可以不用管。
首先想到了283题,Move Zeroes(https://leetcode.com/problems/move-zeroes/) ,用两个指针,不断将0/val移动到数组末端。
但本题要求返回新数组的长度,不只是维护一个长度数字那么简单,经过试错,需要考虑到所有数字都是val、nums中没有元素的情况,都应返回0:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
public int removeElement(int[] nums, int val) {
if (nums == null || nums.length == 0)
return 0;

int len = nums.length;
int slow = 0, fast = 0;

while (fast < nums.length) {
if (nums[fast] == val)
len--;
if (nums[fast] != val && nums[slow] == val) {
nums[slow] = nums[fast];
nums[fast] = val;
}
if (nums[slow] != val)
slow++;
fast++;
}

if (nums[0] == val)
return 0;
return len;
}
}

因为不用考虑新数组的新长度之后的元素,所以只要一次遍历就可以统计出新数组的新长度,同时只要不断将不等于val的值向前压缩即可(类似Move Zeroes解法一):

1
2
3
4
5
6
7
8
9
public class Solution {
public int removeElement(int[] nums, int val) {
int newLen = 0;
for (int i = 0; i < nums.length; i++)
if (nums[i] != val)
nums[newLen++] = nums[i];
return newLen;
}
}

参考:
http://www.programcreek.com/2014/04/leetcode-remove-element-java/