题目简介:
给定一个非负整数数组 A
, A 中一半整数是奇数,一半整数是偶数。
对数组进行排序,以便当 A[i]
为奇数时,i
也是奇数;当 A[i]
为偶数时, i
也是偶数。
你可以返回任何满足上述条件的数组作为答案。
示例:
1 2 3
| 输入:[4,2,5,7] 输出:[4,5,2,7] 解释:[4,7,2,5],[2,5,4,7],[2,7,4,5] 也会被接受。
|
提示:
2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000
思路:
首先将数组A
整个赋值给res
,并在其基础上修改res
。
若当前位置的元素不符合要求,即left % 2 == 0 && res[left] % 2 == 1
或者left % 2 == 1 && res[left] % 2 == 0
时,right
向右移动找到第一个符合交换要求的元素,并与res[left]
交换。
每次遍历结束时,left++, right = left + 1
。
由于给定的数组必是一半奇数,一半偶数,所以依次遍历交换后必为一种答案。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| class Solution { public: vector<int> sortArrayByParityII(vector<int>& A) {
vector<int> res(A);
int left = 0; int right = 1;
while(left < res.size() && right < res.size()){
if(left % 2 == 0 && res[left] % 2 == 1){
while(right < A.size() && (right % 2 != 1 || res[right] % 2 != 0) ) right++; if(right < A.size()) swap(res[left], res[right]); } else if(left % 2 == 1 && res[left] % 2 == 0){
while(right < res.size() && (right % 2 != 0 || res[right] % 2 != 1) ) right++;
if(right < res.size()) swap(res[left], res[right]); }
left++; right = left + 1; }
return res; } };
|