Remove Numbers in Array

Remove Numbers in Array

Given an array and a value, how to implement a function to 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.

Naive Thinking:要求是in-place，那可以通过指针后移或者替换，替换的话顺序会变，这里正好让变。设置一头一尾的指针，从头遍历一旦遇到该value，就与尾部的数替换，最后头指针停留位置就是有效长度。

算法复杂度是O(n)

public class Solution{
    public static void main(String args[]){
        Solution s = new Solution();
        int num[] = {1,1,2,2,3,0,1,4,2,1,4,5};
        int l = s.removeNumberInArray(num,1);
        for(int i = 0;i < l;i++)
            System.out.println(num[i]);
    }
    public int removeNumberInArray(int[] num, int target){
        int i = 0, j = num.length-1;
        while(i < j){
            if(num[i]==target){
                int temp = num[j];
                num[j] = num[i];
                num[i] = temp;
                j--;
            }else{
                i++;
            }
        }
        if(num.length==0){return 0;}
        return num[i]==target?i:i+1;
    }
}

Improved Way:才发现这题和我面试遇到的那道题一样，可以用两个指针一快一慢的遍历。


算法复杂度也是O(n)，但很明显这样要机智很多。


public int removeNumberInArray(int[] num, int target){
        int i = -1,j = 0;
        while(++i < num.length){
            if(num[i] != target)
                num[j++] = num[i];
        }
        return j;
    }