Keshawn_lu's Blog

Leetcode 922. 按奇偶排序数组 II

字数统计: 388阅读时长: 1 min
2020/11/14 Share

题目简介:

给定一个非负整数数组 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] 也会被接受。

提示:

  1. 2 <= A.length <= 20000
  2. A.length % 2 == 0
  3. 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;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: