The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Idea: The basic idea is to move the matched instances to the end of the array. Use two pointers i, j. i moves from left to right, j moves from right to left. Whenever i is pointing to an instance, swap (num[i], num[j]), move j leftward (do not move i since num[j] may also be an instance); otherwise move i rightward.
Time: O(n) Space: O(1)
Code:
public class Solution {
public int removeElement(int[] A, int elem) {
int i=0;
int j=A.length-1;
while(i<=j)
{
if(A[i]==elem)
{
swap(A,i,j);
j--;
}
else
i++;
}
return j+1;
}
public void swap(int[] A, int i,int j)
{
int tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}
}
No comments:
Post a Comment