题目
给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
(时间复杂度不能超过N^2)
示例
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
题干
A 中一半整数是奇数，一半整数是偶数
A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。 也就是 奇下标奇值 偶下标偶值
有什么特点 - 不符合条件的数一定是成对出现的
重点在于 不符合条件的值之间如何交换 满足条件
思路
咋一看这题 暴力解法是肯定可以解的
首先循环数组 一个个找出不符合条件的 找到之后 循环剩下的直到也找到不符合条件的进行交换 直到循环结束
这样的时间复杂度在N^2 是不符合条件的
所以我们要利用空间 特性来解题
空间解法
循环数组 不符合条件的值取出
偶数一个数组 奇数一个数组 原数组= -1
再循环找到-1 根据下标的奇偶性 从数组中取1赋值 直到结束
双指针算法
指针i 指向偶数位 指针j 指向位奇数
while循环 i每次进2 如果找到不符合的停止 让j进2
两个都找到之后交换 直到循环结束
解答
空间解法
class Solution {
public int[] sortArrayByParityII(int[] nums) {
List<Integer> odds = new ArrayList();
List<Integer> evens = new ArrayList();
for(int i=0;i<nums.length;i++){
int value = nums[i];
if(!isSame(i,value)){
nums[i] = -1;
if(isOdd(value)){
odds.add(value);
}else {
evens.add(value);
}
}
}
int oddIndex = 0;
int evenIndex = 0;
for(int i=0;i<nums.length;i++){
int value = nums[i];
if(value == -1){
if(isOdd(i)){
int lastElement = odds.get(oddIndex);
nums[i] = lastElement;
oddIndex++;
}else {
int lastElement = evens.get(evenIndex);
nums[i] =lastElement;
evenIndex++;
}
}
}
return nums;
}
public static boolean isSame(int i,int value){
return (isOdd(i)&& isOdd(value))||(!isOdd(i)&&!isOdd(value));
}
public static boolean isOdd(int num){
return num%2!=0;
}
}
双指针算法
class Solution {
public int[] sortArrayByParityII(int[] A) {
int n = A.length;
int j = 1;
for (int i = 0; i < n; i += 2) {
if (A[i] % 2 == 1) {
while (A[j] % 2 == 1) {
j += 2;
}
swap(A, i, j);
}
}
return A;
}
public void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
时空复杂度分析
如果采用空间解法 时间复杂度为O(2n) 空间复杂度为O(2n)
如果采用双指针算法 时间复杂度为O(N) 空间复杂度为O(n)
结语
抓住特性非常重要 并且双指针是解决交换问题的利器 需要牢牢掌握
