题目描述
给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
要求所有奇数的相对顺序保持不变，所有偶数的相对顺序也保持不变。
如排序前为[1,2,3,4]，其中奇数1排在奇数3之前，偶数2排在偶数4之前，排序后还需要保留这个顺序。
所以排序正确的答案应该为[2,1,4,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
数据结构
- 数组
算法思维
- 遍历、双指针
解题要点
- 使用双指针控制奇数数字和偶数数字放入目标数组中的位置
解题思路
一. Comprehend 理解题意
- 原始数组中有一半的奇数和一半的偶数，元素无序
可以想象成是由两个线程“抢夺”形成的：
一个线程负责将一个 奇数数组 中的元素插入到原始数组中
另一个线程负责将一个 偶数数组 中的元素插入到原始数组中 - 排序后的新数组必须是 偶数-奇数-偶数-奇数 交替的
且不能改变 奇数数组 和 偶数数组 内部元素的原有顺序
二. Choose 选择数据结构与算法
用双指针遍历原始数组
- 数据结构：数组
- 算法思维：遍历、双指针
解题思路
- 用奇偶两指针遍历 原数组A
- 将奇偶指针位置上的元素交替插入 新数组B 中
三. Code 编码实现基本解法
class Solution {
public int[] sortArrayByParityII(int[] A) {
int len = A.length;
int odd = 0;
int even = 0;
int[] B = new int[len];
int indexB = 0;
while (odd < len && even < len){
while (A[even] % 2 != 0){
even++;
}
B[indexB++] = A[even++];
while (A[odd] % 2 != 1){
odd++;
}
B[indexB++] = A[odd++];
}
return B;
}
}
执行耗时：4 ms，击败了 31.62% 的Java用户
内存消耗：41.2 MB，击败了 33.78% 的Java用户
时间复杂度：O(n)
• 奇数指针遍历一次 原数组A O(n)
• 偶数指针遍历一次 原数组A O(n)
• 新数组B的 n 次插入操作 O(n)
空间复杂度：O(n)
• 新数组B 的内存空间 O(n)
• 三个整型指针变量的内存空间 O(1)
四. Consider 思考更优解
改变算法思维：双指针的遍历对象：原始数组 => 结果数组
- 用奇偶两指针遍历 新数组B
奇数指针起始索引为1，步长为2
偶数指针起始索引为0，步长为2 - 遍历 原始数组A ，根据元素奇偶性插入 新数组B 的奇/偶索引位置
五. Code 编码实现最优解
class Solution {
public int[] sortArrayByParityII(int[] A){
int even = 0;
int odd = 1;
int[] B = new int[A.length];
for (int a : A){
if (a % 2 == 0){
B[even] = a;
even += 2;
} else {
B[odd] = a;
odd += 2;
}
}
return B;
}
}
执行耗时：3 ms，击败了 78.92% 的Java用户
内存消耗：41.3 MB，击败了 30.58% 的Java用户
时间复杂度：O(n)
• 一次 原始数组A 的遍历 O(n)
• 一次 新数组B 的逐位插入 O(n)
空间复杂度：O(1)
• 新数组B 的内存空间 O(n)
• 两个整型指针变量的内存空间 O(1)
六. Change 变形与延伸
=== 待续 ===
