leetcode-27 Remove Element
来源：程序员人生 发布时间：2015-05-14 09:37:11 阅读次数：3011次
问题描写：
Givenan array and a value, remove all instances of that value in place and returnthe new length.
The order of elements can be changed. It doesn'tmatter what you leave beyond the new length.
问题分析：
此算法的关键在于数组元素的移动，当遇到1个A[i]==elem时通过数组后面所有元素前移的方法性能较差，下面对此进行了优化。
方法1：双指针法，当start处的元素需要移除时，使用end处元素进行填充
但要注意end处的元素也为elem，故交换start和end元素后，注意start不递增
方法2：统计当前遍历的i长度数组内，需要移除的elem个数removeCount，则可以将A[i]移到A[i - removeCount]处，
此方法较于上个方法，时间复杂度优劣取决于elem的个数，若需要移除的元素个数较多，则此方法较优；否则，方法1较优
代码：
/*
方法1：双指针法，当start处的元素需要移除时，使用end处元素进行填充
但要注意end处的元素也为elem，故交换start和end元素后，注意start不递增
*/
public class Solution {
public int removeElement(int[] A, int elem) {
if(A == null || A.length == 0)
return 0;
int start = 0;
int end = A.length - 1;
while(start < end)
{
//问题的关键在于移动数组中的元素
if(A[start] == elem)
A[start] = A[end--];
else
start++;
}
return A[start] == elem ? start : start + 1;
}
}
/*
方法2：统计当前遍历的i长度数组内，需要移除的elem个数removeCount，则可以将A[i]移到A[i - removeCount]处，
此方法较于上个方法，时间复杂度优劣取决于elem的个数，若需要移除的元素个数较多，则此方法较优；否则，方法1较优
*/
public class Solution {
public int removeElement(int[] A, int elem) {
int removeCount = 0;
for(int i = 0 ; i < A.length ; i++){
if(A[i] == elem)
removeCount++;
else
A[i - removeCount] = A[i];
}
return A.length - removeCount;
}
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
