# 922. Sort Array By Parity II

2018/10/14 21:29

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.


Note:

1. 2 <= A.length <= 20000
2. A.length % 2 == 0
3. 0 <= A[i] <= 1000

#include<vector>
#include <cstdlib>
#include<iostream>
#include <unordered_set>
#include <algorithm>
#include<string>
#include<queue>

using namespace std;

//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.
//Note:
//
//2 <= A.length <= 20000
//A.length % 2 == 0
//0 <= A[i] <= 1000

class Solution {
public:
vector<int> sortArrayByParityII(vector<int> &A) {
int i = -1;
int n = A.size();
for (int j = 0; j < n; j = j + 2) {
if (A[j] % 2 == 0) {
continue;
} else {
//A[j]%2==1 at this moment
i += 2;
while (A[i] % 2 == 1)
i += 2;
//A[i]%2==0 at this monent
//cout << "i " << i << " j " << j << endl;
swap(A[i], A[j]);
}
}
return A;
}
};

int main() {

Solution solution;
vector<int> A{4, 2, 5, 7};
vector<int> res = solution.sortArrayByParityII(A);
for (auto a:res)
cout << a << " ";
cout << endl;
return 0;
}

0
0 收藏

0 评论
0 收藏
0