LeetCode 26 - Remove Element

Rafal's Blog - LeetCode 26 – Remove Element
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.

The idea is to look for elem from the left, and swap into its place something from the right of the array, so that all elems are at the end of the array

public int removeElement(int[] A, int elem) {
  int oldLength = A.length;
  int removed = 0;
  int lastValidIndex = A.length-1;

  int i = 0;
  while(i <= lastValidIndex){
    if(A[i] == elem){
      A[i] = A[lastValidIndex];
      lastValidIndex--;
      removed++;
    } 
    else{
      i++; 
    }
  }
  return oldLength - removed;
}

https://discuss.leetcode.com/topic/1228/my-solution-for-your-reference

int removeElement(int A[], int n, int elem) {
    int begin=0;
    for(int i=0;i<n;i++) if(A[i]!=elem) A[begin++]=A[i];
    return begin;
}

http://ithelp.ithome.com.tw/question/10160140

1. public int removeElement(int[] data, int elem)  
2. {  
3.     int index = 0;  
4.     for (int i = 0; i < data.Length; i++)  
5.     {  
6.         if (data[index] == elem && data[i] != elem)                  
7.         {  
8.             data[index] = data[i];  
9.             index++;  
10.             data[i] = elem;  
11.         }  
12.         else if (data[index] != elem && data[i] != elem)  
13.         {  
14.             index++;  
15.         }  
16.     }  
17.     return index;  
18. } 

https://leetcode.com/articles/remove-element/

  public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
      if (nums[j] != val) {
        nums[i] = nums[j];
        i++;
      }
    }
    return i;
  }

When elements to remove are rare

Now consider cases where the array contains few elements to remove. For example, $nums = [1,2,3,5,4], val = 4$. The previous algorithm will do unnecessary copy operation of the first four elements. Another example is $nums = [4,1,2,3,5], val = 4$. It seems unnecessary to move elements $[1,2,3,5]$ one step left as the problem description mentions that the order of elements could be changed.

When we encounter $nums[i] = val$, we can swap the current element out with the last element and dispose the last one. This essentially reduces the array's size by 1.

In this solution, the number of assignment operation is equal to the number of elements to remove. So it is more efficient if elements to remove are rare.

  public int removeElement(int[] nums, int val) {
    int i = 0;
    int n = nums.length;
    while (i < n) {
      if (nums[i] == val) {
        nums[i] = nums[n - 1];
        // reduce array size by one
        n--;
      } else {
        i++;
      }
    }
    return n;
  }

http://www.cnblogs.com/EdwardLiu/p/3703444.html
Related: Remove Elements from Array
Read full article from Rafal's Blog - LeetCode 26 – Remove Element