剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

首尾

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int end = nums.size() - 1;
        for(int i = 0; i < end; ++i)
        {
            while(i < end && nums[i] % 2 == 0)
                swap(nums[i], nums[end--]);
        }
        return nums;
    }
};

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int begin = 0, end = nums.size() - 1;
        while(begin < end)
        {
            if(nums[begin] & 1)
                ++begin;
            else if(!(nums[end] & 1))
                --end;
            else
                swap(nums[begin], nums[end]);
        }
        return nums;
    }
};

快慢

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        // 慢指针用来记录可以放奇数的位置，快指针用来搜索后面的所有奇数，如果是奇数，就把他换到前面去
        int walker = 0, runner = 0;
        while(runner < nums.size())
        {
            if(nums[runner] & 1)
                swap(nums[walker++], nums[runner]); // 从walker换过来是奇数是不可能的，因为之前已经处理过了
            ++runner;
        }
        return nums;
    }
};