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;
}
};
