RemoveElement [source code]

public class RemoveElement {
static
/******************************************************************************/
public class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0) return 0;
        int tail = nums.length - 1;
        int i = 0;
        while (i < tail) {
            if (nums[i] == val) {
                while (tail > i && nums[tail] == val) tail--;
                if (tail == i) break;
                nums[i++] = nums[tail--];
            } else i++;
        }
        if (nums[tail] == val) tail--;
        return tail + 1;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        RemoveElement.Solution tester = new RemoveElement.Solution();
        int[] input1 = {3,2,2,3};
        System.out.println(tester.removeElement(input1, 3));
        Printer.array (input1);
        int[] input2 = {1,2,3,4,5,6,7};
        System.out.println(tester.removeElement(input2, 3));
        Printer.array (input2);
        int[] input3 = {1,2,3,2,5,2,7};
        System.out.println(tester.removeElement(input3, 2));
        Printer.array (input3);
    }
}

这题思路还是很清晰的, 就是要想到一个 swap 来做, 而不是用 shift(这个最后会有 N^2的时间);
刚开始一个难点没有想通, 这里你传进来的 nums, 我们最后返回的 nums 的长度肯定是一样的, 多余的部分怎么 deallocate? 后来看了一下他们给的 example, 好像大概意思就是, 你只要保证前 newLengh 给 element 全都是被 remove 干净之后的就行了;
这个可能也是为什么你最后的返回值应该是 new length 的原因; 类似于是一个argument of valid range 的作用;

虽然这里没有用到, 不过写的时候想到一个问题, 就是一个conditional increment的问题:
并不是每一个 iteration 你都要强制一定要 increment loopvar, 之前见过的一个代码就是, 有时候一个 iteration 就完全不 increment, 这个 iteration 完成的内容只包含对 nums 的操作, 然后下一个 iteration 如果满足了某一个条件, 就可以 increment;

写这个

while (i < tail) {

的时候, 想不清楚是否应该取等号, 当时使用的例子是: [3,2,2,3], 这个例子相对这个可能有点复杂; 我立刻就干脆换了一个例子: [1,2,3,4,5]/3, 这个就相对简单很多, 然后考虑是否应该让相等的情况也进入 loop 接受body 的处理; 后来认为不应该, 这个时候就应该结束了;

这里的算法的核心思路还是很清晰的, 就是保证 i 所指向的位置一定不是 val;

另外这一题还是测试了Empty Case, 如果没有检查的话就吃亏了;

这个内循环刚开始的想法是这样写的:

while (nums[tail] == val && tail >= i) tail--;

但是这个就不对. header 里面的&&并列的时候的顺序是非常有讲究的, 之类应该把 tail 的范围判断放在前面; 然后你后面才可以进行对 tail 位置的 access: 第二个 term 依赖于第一个 term 的成功; 这个习惯感觉还是有待锻炼;

另外上面这个 header 就算是调换顺序之后其实还是不对, 正确的顺序应该是:

while (tail > i && nums[tail] == val) tail--;

因为这里不能取等号? 为什么不能取等号因为你最后想要的termination condition是tail == i: the terminating condition should fail the header test; 你要清楚你希望最后停在什么位置, what state TRIGGERS the header FAILURE;

最后的速度只有9(66), 有点吃惊, 因为这个算法虽然有两个循环, 但是实际的速度应该只有2N;

这个是 submission 最优解: 8(96):

public class Solution {  
    public int removeElement(int[] A, int elem) {  
        int len = A.length;  
        for (int i = 0 ; i< len; ++i){  
            while (A[i]==elem && i< len) {  
                A[i]=A[--len];  
            }  
        }  
        return len;  
    }  
}

感觉整体算法跟我的差不多, 就是简化了很多写法上的细节;

这个是 editorial 上面看到的一个最优解:

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;  
}

这个思路是很有意思的; 类似之前那个 remove0的题目的思路, 两个 pointer 同向不同速的移动; 这样最后的 termination 很好判断; 只要直接通过 j 来判断就行了; 而且这个算法可以立刻为是一个not in place版本的直接翻译过来: 直接把 not InPlace 版本的基础上, 把 argument 作为 res 就是这个算法了;

这个是 editorial 的另外一个解:

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;  
}

这个解就用到了上面提到的conditional increment的技巧, 这个技巧就避免了我第二个 loop 的使用; 我的做法是当我们在i 碰到 val 之后, 我们移动 tail, 直到 tail 找到一个不等于 val 的值;
这里这个逻辑则更加清晰: 我们在 i 碰到 val 的话, 不管三七二十一先把 tail 的那个拿过来, 然后 tail 向前移动(因为当前 tail 指向的这个已经被复制过了). 然后下一个 iteration, 如果我们发现 i 的位置还是 val(也就是上一个 tail 移动过来的这个 element 其实还是 val), 我们继续把当前的 tail 指向的拿过来, 然后 tail--. 注意这两个 iteration 当中, i 都是没有动的! 只有发现 i 指向的位置不是 val 的时候, 我们才 i++(可以说这个也是一个 invariant);

discussion上面并没有其他的更好的解了. 这一题的 editorial 的质量倒是挺给力的;

Problem Description

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Difficulty:Easy
Category:Algorithms
Acceptance:38.60%
Contributor: LeetCode
Related Topics
array two pointers
Similar Questions
Remove Duplicates from Sorted Array Remove Linked List Elements Move Zeroes