leetcode-27 Remove Element
发布时间：2020-12-13 20:10:01 所属栏目：PHP教程 来源：网络整理
导读：问题描写： 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. 问题分析： 此算法的关键在于数组元素的移
|
问题描写： 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;
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |