Leetcode283

LeetCode283：移动零         给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

方法一：空间局部优化 (执行用时:16ms 内存消耗：9.3MB)

class Solution {
public:
    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];
        }
    }
};

方法二：空间最优，操作局部优化（双指针）(执行用时:8ms 内存消耗：8.8MB)

class Solution2 {
public:
    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;
        }
    }
};

方法三：最优解 (执行用时:8ms 内存消耗：9.1MB)

/****************************************************************************************************************************
方法三：最优解 (执行用时:8ms 内存消耗：9.1MB)

前一种方法的操作是局部优化的。例如，所有（除最后一个）前导零的数组：[0，0，0，…，0，1]。对数组执行多少写操作？
对于前面的方法，它写 0 n-1n−1 次，这是不必要的。我们本可以只写一次。怎么用？… 只需固定非 0 元素。
最优方法也是上述解决方案的一个细微扩展。一个简单的实现是，如果当前元素是非 0 的，那么它的正确位置最多可以是当前位置或者更早的位置。
如果是后者，则当前位置最终将被非 0 或 0 占据，该非 0 或 0 位于大于 “cur” 索引的索引处。
我们马上用 0 填充当前位置，这样不像以前的解决方案，我们不需要在下一个迭代中回到这里。
换句话说，代码将保持以下不变：
慢指针（lastnonzerofoundat）之前的所有元素都是非零的。
当前指针和慢速指针之间的所有元素都是零。
因此，当我们遇到一个非零元素时，我们需要交换当前指针和慢速指针指向的元素，然后前进两个指针。如果它是零元素，我们只前进当前指针。
********************************************************************************************************************************/
class Solution3 {
public:
    void moveZeroes(vector<int>& nums) {
        for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.size(); cur++) {
            if (nums[cur] != 0) {
                swap(nums[lastNonZeroFoundAt++], nums[cur]);
            }
        }
    }
};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;


int main()
{
    vector<int> nums;
    int Size = 0;
    cout << "请输入数组的大小 Size: " << endl;
    cin >> Size;
    cout << "请输入数组的元素： " << endl;
    int Currval;
    for (int i = 0; i < Size; i++)
    {
        cin >> Currval;
        nums.push_back(Currval);
    }

    Solution2 answer;
    answer.moveZeroes(nums);
    for (auto n : nums)
        cout << n << " ";

    system("pause");
    return 0;
}