922. Sort Array By Parity II。

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.
Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.
You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

原文链接：https://leetcode.com/problems/sort-array-by-parity-ii/

给定一个数组，其中奇数和偶数各一半，要求返回的数组中，奇数下标中的元素为奇数，偶数索引下标中的元素为偶数。

最简单的做法就是将原数组中的元素进行分开存放，然后再将这些元素按照要求组装起来。

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int i,even_index=0,odd_index=0;
        vector<int> odds,evens;
        for(int i : A) {
            if(i%2 == 0)
                evens.push_back(i);
            else
                odds.push_back(i);
        }
        for(i=0;i<A.size();i++){
            if(i%2==0) {
                A[i] = evens[even_index];
                even_index++;
            } else {
                A[i] = odds[odd_index];
                odd_index++;
            }
        }
        return A;
    }
};

显然上述做法并不明智，既浪费了时间又浪费了空间。我们可以在此基础上优化一下，可以先申请一个与原来数组大小相同的结果数组。遍历原先的数组，如果遇到了奇数元素就将该元素放置到结果数组中的奇数位置上，如果是偶数元素则放置到结果数组中的偶数位置上。

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int i,even_index=0,odd_index=1;
        vector<int> result(A.size(),0);
        for(i=0;i<A.size();i++) {
            if(A[i]%2==0) {//如果当前数字为偶数，则将该数字放到结果数组中的偶数索引上
                result[even_index] = A[i];
                even_index += 2;
            } else {
                result[odd_index] = A[i];
                odd_index += 2;
            }
        }
        return result;
    }
};

可以看到上述两个方法都是O(n)的空间复杂度，那么接下来的优化可以从缩小空间复杂度入手，一个不难想到的做法就是如果当前索引是奇数但是元素不是奇数，那么就找到下一个奇数元素进行交换，偶数也是如此。

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int i,even_index,odd_index;
        for(i=0;i<A.size();i++) {
            even_index = odd_index = i;
            if(i%2 == 0) {//当前为偶数索引
                while(A[even_index]%2!=0 && even_index<A.size()) {//找到下一个偶数
                    even_index++;
                }
                swap(A[i],A[even_index]);
            } else {//当前为奇数索引
                while(A[odd_index]%2==0 && odd_index<A.size()) {//找到下一个奇数
                    odd_index++;
                }
                swap(A[i],A[odd_index]);
            }
        }
        return A;
    }
};

显然上面一个方法，冗余了很多循环。我们可以对奇数索引进行检查，如果是奇数元素的话，就检查下一个奇数索引，直到发现奇数索引上不是奇数元素停止，然后按照此方法检查偶数索引，最后将其进行交换。

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int even_index=0,odd_index=1;
        while(even_index<A.size() && odd_index<A.size()) {
            while(A[even_index]%2==0&&even_index<A.size()) even_index+=2;//偶数索引不为偶数时停下来
            while(A[odd_index]%2==1&&odd_index<A.size()) odd_index+=2;//奇数索引不为奇数时停下来
            //cout << A[even_index] << ",index:" << even_index << endl;
            //cout << A[odd_index] << ",index:" << odd_index << endl;
            if(even_index>A.size() || odd_index>A.size()) break;
            swap(A[even_index],A[odd_index]);
        }
        return A;
    }
};

另一种写法：

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) 
    {
        for(int i=0,j=1;i<A.size()&&j<A.size();)
        {
            if(A[i]%2==0)
                i+=2;
            else if(A[j]%2==1)
                j+=2;
            else
                swap(A[i],A[j]);
        }
        return A;
    }
};