27. 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.

链接： http://leetcode.com/problems/remove-element/

一刷，做不到一遍bug free。19行比较有意思，因为left, right相对位置判断在值判断之前，当两个下标重合时，至少有一个是不符合第二个条件的，所以要判断当前值是否等于val。此解法从首尾各用一个下标，尾部的!=val直接填在前面，中间的不需要动。

另一种解法是从开头用2个下标的缺点是，除了最开始的一些元素，所有!=val的值都会被赋值一次。

3,2,2,3 val=3这个例子中，第一种解法只需要赋值1次，另外一种需要赋值2次。

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        if not nums:
            return 0
        left = 0
        right = len(nums) - 1
        length = len(nums)

        while left <= right:
            while left < right and nums[left] != val:
                left += 1
            while right > left and nums[right] == val:
                right -= 1
            if left == right:
                return left + 1 if nums[left] != val else left
            nums[left] = nums[right]
            left += 1
            right -= 1
        return left

2/11/2017, Java

错误：

第5行，b初始值应该是nums.length - 1

想到一个对待简单题下标的窍门，对每个下标的意义要清楚，不要仅仅是从前面的下标是f，从后面的下标是b。正确的方法是，f代表将要被比较可能被修改的值，b代表从后面开始未比较的而且不同于目标的值。

public class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums == null) return 0;
        int f = 0;
        int b = nums.length - 1;
        while (b >= 0 && nums[b] == val) b--;
        if (b < 0) return 0;

        while (f <= b) {
            if (nums[f] == val) {
                nums[f] = nums[b--];
                while (nums[b] == val) b--;
            }
            f++;
        }
        return f;
    }
}