当前位置 博文首页 > zhouyu的博客：LeetCode题解第922题
LeetCode第922题：
922.按奇偶排序数组2
1.思路：两个指针分别遍历数组直到其值分别奇数和偶数，若新数组下标为奇数，则奇数存入，奇数下标后移，若数组下标为偶数，则偶数存入，偶数下标后移。
class Solution {
public int[] sortArrayByParityII(int[] A) {
int p=0,q=0,index=0;
int len = A.length;
int[] B = new int[len];
while(true){
//找下一个奇数的下标
while(p < len){
if(A[p] % 2 == 1){
break;
}
p++;
}
//找下一个偶数的下标
while(q < len){
if(A[q] % 2 == 0){
break;
}
q++;
}
//判断新数组下标存储值
if(index % 2 == 0){
B[index] = A[q];
q++;
}else{
B[index] = A[p];
p++;
}
index++;
if(index >= len){ //所有数均以存储，跳出循环
break;
}
}
return B;
}
}
2.思路：两次遍历，第一次将偶数放在新数组的偶数下标下，第二次将奇数放在新数组奇数下标下
class Solution {
public int[] sortArrayByParityII(int[] A) {
int[] B = new int[A.length];
//第一次遍历将偶数放在新数组的偶数下标下
int i = 0;
for (int x : A) {
if (x % 2 == 0) {
B[i] = x;
i += 2;
}
}
//第二次遍历将奇数放在新数组奇数下标下
i = 1;
for (int x : A) {
if (x % 2 == 1) {
B[i] = x;
i += 2;
}
}
return B;
}
}
3.思路：两个指针i，j作为下标分别遍历数组的偶数和奇数部分，如果A[i]为奇数，则不断使j前移（每次加2），直到A[j]为偶数，然后交换A[i]与A[j]的值。直到i遍历完完了偶数部分，所有的数就都在正确的位置了
class Solution {
public int[] sortArrayByParityII(int[] A) {
int i = 0, j = 1;
int len = A.length;
while(i < len){
if(A[i] % 2 == 1){//如果偶数下标位置的数为奇数
while(true){//找到奇数位置中值为偶数的下标并交换值
if(A[j] % 2 == 0){
int t = A[i];
A[i] = A[j];
A[j] = t;
break;
}
j += 2;
}
}
i += 2;
}
return A;
}
}
