题目地址
难度：⭐
题目描述：
给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
你可以返回满足此条件的任何数组作为答案。
示例：
1
2
3
| 输入：[3,1,2,4]
输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
|
提示：
1 <= A.length <= 50000 <= A[i] <= 5000
🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️解题过程🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️
解题过程：
思路：
已经做过一道类似的题目了按奇偶排序数组II，这道题的进阶版反而被我先做了🤣，下面给出两种方法
①遍历：定义一个数组result存储排序后的结果，遍历数组A，对偶数元素从左往右存储到result中，对奇数元素从右往左存储到result中。
②双指针：一个指针i指向数组A开头，指针j指向第一个奇数元素，然后遍历A，如果指针i指的是奇数元素就从j开始找到一个偶数元素和i指针元素交换，这里指针其实就是数组下标。
方法一：遍历
c++代码：(执行用时16ms，击败83.57%，内存消耗16M，击败34.25%）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> sortArrayByParity(vector<int>& A) {
vector<int> result(A);
int odd=A.size()-1,even=0;
for(int i:A){
if(i%2==0){
result[even]=i;
++even;
}else{
result[odd]=i;
--odd;
}
}
return result;
}
};
|
方法二：双指针
c++代码：(执行用时16ms，击败83.66%，内存消耗16M，击败29.77%）
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
| class Solution {
public:
vector<int> sortArrayByParity(vector<int>& A) {
int n=A.size();
int i=0,j=0;
for(i=0;i<n;++i){
if(A[i]%2==1){
j=i;
break;
}
}
for(i=0;i<n;++i){
if(A[i]%2==1){
while(j<n && A[j]%2==1){
++j;
}
if(j<n){
swap(A[i],A[j]);
++j;
}else{
break;
}
}
}
return A;
}
};
|
方法 1：排序
想法和算法
使用排序算法，按照模 2 的结果排序。
Java代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int[] sortArrayByParity(int[] A) {
Integer[] B = new Integer[A.length];
for (int t = 0; t < A.length; ++t)
B[t] = A[t];
Arrays.sort(B, (a, b) -> Integer.compare(a%2, b%2));
for (int t = 0; t < A.length; ++t)
A[t] = B[t];
return A;
}
}
|
复杂度分析
- 时间复杂度：$O(N\log N)$，其中 N 是
A 的长度。
- 空间复杂度：排序空间为 $O(N)$，取决于内置的
sort 函数实现。
方法 2：两边扫描
想法和算法
第一遍输出偶数，第二遍输出奇数。
Java代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int[] sortArrayByParity(int[] A) {
int[] ans = new int[A.length];
int t = 0;
for (int i = 0; i < A.length; ++i)
if (A[i] % 2 == 0)
ans[t++] = A[i];
for (int i = 0; i < A.length; ++i)
if (A[i] % 2 == 1)
ans[t++] = A[i];
return ans;
}
}
|
复杂度分析
- 时间复杂度：$O(N)$，其中 $N$ 是
A 的长度。
- 空间复杂度：$O(N)$，存储结果的数组。
方法 3：原地算法
想法
如果希望原地排序，可以使用快排，一个经典的算法。
算法
维护两个指针 i 和 j，循环保证每刻小于 i 的变量都是偶数（也就是 A[k] % 2 == 0 当 k < i），所有大于 j 的都是奇数。
所以， 4 种情况针对 (A[i] % 2, A[j] % 2)：
- 如果是
(0, 1)，那么万事大吉 i++ 并且 j--。
- 如果是
(1, 0)，那么交换两个元素，然后继续。
- 如果是
(0, 0)，那么说明 i 位置是正确的，只能 i++。
- 如果是
(1, 1)，那么说明 j 位置是正确的，只能 j--。
通过这 4 种情况，循环不变量得以维护，并且 j-i 不断变小。最终就可以得到奇偶有序的数组。
Java代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[] sortArrayByParity(int[] A) {
int i = 0, j = A.length - 1;
while (i < j) {
if (A[i] % 2 > A[j] % 2) {
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
if (A[i] % 2 == 0) i++;
if (A[j] % 2 == 1) j--;
}
return A;
}
}
|
复杂度分析
- 时间复杂度：$O(N)$，其中 $N$ 是
A 的长度。循环的每一步都让 j-i 至少减少了一。（注意虽然快排的复杂度是 $O(N\log N)$，但是我们只需要一轮扫描就可以了）。
- 空间复杂度：$O(1)$，不需要额外空间。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：
官方题解给出了3种解法，第一种排序就是根据模2的结果排序（偶数是0，奇数是1）；第二种方法优化一下遍历一次就是我第一种方法；第三种方法原地算法其实就是双指针，只不过比我的要更简便一些，我是没有想到第二个指针从右边开始遍历，最后结束条件是两个指针i和j做比较，我是两个指针都有它们各自的遍历范围，没想到两个指针比较作为结束条件，双指针解法还是挺灵活的。
