Friday, January 2, 2015

Remove Element (LeetCode Array)

Question: Given an array and a value, remove all instances of that value in place and return the new length.
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