题目解析

Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
Example 1:
Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
It doesn’t matter what you leave beyond the returned length.

整型数组中移除和目标val相同的元素,返回剩下数据的长度n,数组前n元素是结果元素

分析步骤

1、返回非val元素个数n,并且数组前n是非val 元素, 注意顺序无要求
2、除去n个元素外剩余的元素内容也没要求
3、不开辟额外的数组空间

代码演示:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Given an array nums and a value val, remove all instances of that value in-place and return the new length.
*
* Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
*
* The order of elements can be changed. It doesn't matter what you leave beyond the new length.
* 分析 :直接方案是遍历数组 遇到和val相同的元素 与后面不和val相同的元素交换
* 此处小技巧, 后面不同于val的元素可以按照倒序来交换
* 实现相对较OK 优于99.85%的提交
*/
public class A27RemoveElement {
public int removeElement(int[] nums, int val) {
int counter = 0;
int end = nums.length - 1; // end标记需要交换的元素
for (int i = 0; i < nums.length; i++) {
if(i > end) break;
if(nums[i] == val){
while (nums[end]==val){// 从尾部向前找 第一个不等于val的元素
end--;
if(end <i){ // 全部是val的情况会导致end < 此时i的值, 返回统计计数
return counter;
}
}
int tmp = nums[i]; // 交换i和end元素位置
nums[i] = nums[end];
nums[end] = tmp;
end--;
counter++; // 和不同于val的元素交换后需要计数++
} else {
counter++; // 不同于val的元素 计数++
}
}
return counter;
}
public static void main(String[] args) {
A27RemoveElement a= new A27RemoveElement();
a.removeElement(new int[]{4,5},5);
}
}

代码文件:
A27RemoveElement.java

总结

  • 顺序思路实现,优化了下小细节, 主要还是防脑袋秀逗。 思考思考,写写

版权声明:本文为博主原创文章,未经允许不得转载。