leetcode-27 Remove Element
來源：程序員人生 發布時間：2015-05-14 09:37:11 閱讀次數：3164次
問題描寫：
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;
}
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
