lintcode373 奇偶分割数组

奇偶分割数组 

分割一个整数数组，使得奇数在前偶数在后。

您在真实的面试中是否遇到过这个题？ 

Yes

样例

给定 [1, 2, 3, 4]，返回 [1, 3, 2, 4]。

我的方法：设定两个数组，分别保存奇偶。使用了额外空间。

时间：340 ms

class Solution {
public:

    void partitionArray(vector<int> &nums) {
        // write your code here
        if (nums.empty()) {
            return;
        }
        vector<int> odd;
        vector<int> even;
        int len = nums.size();
        for (int i = 0; i < len; i++) {
            if (nums[i] % 2) {
                odd.push_back(nums[i]);
            } else {
                even.push_back(nums[i]);
            }
        }

        for (int i = 0; i < even.size(); i++) {
            odd.push_back(even[i]);
        }
        nums = odd;

    }
};

网上别人方法：不使用额外空间。

时间：288 ms

class Solution {
public:
    void partitionArray(vector<int> &nums) {
        int i = 0, j = nums.size() - 1;
        while (i < j) {
            if (0 == nums[i] % 2) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j--;
            } else {
                i++;
            }
        }
        return;
    }
};