Leetcode 283. Move Zeros

283. Move Zeros

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

思路：

看到这题之后不知道为啥第一反应是冒泡...于是上网重新快速复习了一遍排序法，发现其实还是蛮不一样的。最后思路是：每次遇到0就无脑往后移，最终把所有0都移到最后面去。

我的做法：

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        count = 0
        inx = 0
        for x in range(0,len(nums)):
            if nums[inx] == 0:
                for i in range(inx, len(nums)-1-count):
                    temp = nums[i+1]
                    nums[i+1] = nums[i]
                    nums[i] = temp
                count += 1
                inx -= 1
            inx += 1

嗯对是对了，但其实想想这个方法还是有很不合理的地方。比如这个x的取值，意味着无论你后面几个是零或不是零，都需要遍历到最后；而第二个for循环里面，没有任何判别条件，一味把0往后传，也会导致一个结果就是哪怕nums=[0,0,0,0,0]，也会从第一个零开始，一个个把零往后传。虽然最后是accepted，但其实并没有达到步数少的要求。

答案：都是C++版本的，但是看了非常有启示！

方法一：创建一个新向量填数。

void moveZeroes(vector<int>& nums) {
    int n = nums.size();

    // Count the zeroes
    int numZeroes = 0;
    for (int i = 0; i < n; i++) {
        numZeroes += (nums[i] == 0);
    }

    // Make all the non-zero elements retain their original order.
    vector<int> ans;
    for (int i = 0; i < n; i++) {
        if (nums[i] != 0) {
            ans.push_back(nums[i]);
        }
    }

    // Move all zeroes to the end
    while (numZeroes--) {
        ans.push_back(0);
    }

    // Combine the result
    for (int i = 0; i < n; i++) {
        nums[i] = ans[i];
    }
}

创建一个新向量，从原向量那里把非零元素填进去，且计算原向量中0的个数，然后把这么多个零放到新向量后面。其实我感觉也可以指定新向量的长度和原向量一样长，把非零元素填进去之后，直接把剩下的填0。

其实我想说...我也想过这种做法，但是题目说不给copy啊（黑人问号脸.jpg

时间复杂度：O(n)，移动步数并非最优

空间复杂度：O(n)，因为建立了一个新的向量。

方法二：使用两个指针，把非零的数按顺序重新填入向量中。

void moveZeroes(vector<int>& nums) {
    int lastNonZeroFoundAt = 0;
    // If the current element is not 0, then we need to
    // append it just in front of last non 0 element we found. 
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) {
            nums[lastNonZeroFoundAt++] = nums[i];
        }
    }
    // After we have finished processing new elements,
    // all the non-zero elements are already at beginning of array.
    // We just need to fill remaining array with 0's.
    for (int i = lastNonZeroFoundAt; i < nums.size(); i++) {
        nums[i] = 0;
    }
}

把非零的数按顺序重新填入向量中，并计数，计算非零的元素有多少个。比如说5个吧，然后从第6个元素开始就全部填0。感觉有点像有两个指针在移动，一个是i，一个是lastNonZeroFoundAt，lastNonZeroFoundAt会在0处停留，然后把nums[i]填入这个位置之后，lastNonZeroFoundAt才会继续往前走。

时间复杂度：O(n)，步数仍非最优

空间复杂度：O(1)

方法三：使用两个指针，直接把非零值和0交换，比上面的更简洁。

void moveZeroes(vector<int>& nums) {
    for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.size(); cur++) {
        if (nums[cur] != 0) {
            swap(nums[lastNonZeroFoundAt++], nums[cur]);
        }
    }
}

你可以想象有两个人分工合作去找宝贝填入空的坑里面，A和B一起跑，如果坑已经有宝了就都往前走，如果有空的坑，A继续往前走，如果A发现前面的坑有宝，就会把宝丢给B，与此同时A所走到的这个地方的坑就空了（相当于swap），然后A和B都继续往前走。

时间复杂度：O(n)，移动步数最优，有多少个非零值就移动多少次好啦。

空间复杂度：O(1)。

总结：

1. 做出来了，但是步数方面非常不合理，有待改进

2. 学会了两个指针移动这种分工合作填坑的好方法！