27. Remove Element

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 by modifying the input array in-place with O(1) extra memory.

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

Example:

Given nums = [3,2,2,3], val = 3,

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

python3

题目中说数组中的元素不必保持原来的顺序。从后向前扫描，碰到elem时，与尾指针指向的元素交换，将elem换到数组的末尾，然后数组长度减一。

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        end_index = len(nums) - 1
        # from nums[len(nums)] to nums[0] with step -1
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] == val:
                # exchange two value without temp
                nums[i], nums[end_index] = nums[end_index], nums[i]
                end_index -= 1
        return end_index + 1

c++11

顺序遍历，当当前值等于val时，将末尾值赋值给它，同时删除末尾元素。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        for (auto i = 0; i < nums.size(); ) {
            if (nums[i] == val) {
                nums[i] = nums.back();
                nums.pop_back();
            } else i++;
        }
        return nums.size();
    }
};