/*
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
*/
//使用额外数组时 时间O(n) 空间O(n)
//不使用额外数组时 时间O(n^2) 空间O(1)
import java.util.ArrayList;
public class Solution {
public void reOrderArray(int [] array) {
int lengthOfArray = array.length;
ArrayList list1 = new ArrayList<>();
ArrayList list2 = new ArrayList<>();
for(int num:array){
if(num%2==1){
//奇数
list1.add(num);
}else if(num%2==0){
list2.add(num);
}
}
ArrayList list = new ArrayList<>();
list.addAll(list1);
list.addAll(list2);
for(int i = 0;i
array[i] = list.get(i);
}
}
}
import java.util.ArrayList;
public class Solution {
public void reOrderArray(int [] array) {
//不使用额外数组
int i = 0;//记录已经调整好的奇数的下一个位置下标
int j = 0;
for(j=0;j
if(array[j]%2==0){
continue;
}else if(array[j]%2==1){//遇到奇数开始处理
if(j==i){//两个奇数相邻的情况 下标继续移动
i++;
continue;
}else{
int temp = array[j];
for(int x = j-1;x>=i;x--){
array[x+1] = array[x];//数组中 i到j-1的部分向后移动一位(不能直接交换位置，会打乱相对位置)
}
array[i++] = temp;//注意要让i自增
}
}
}
}
}
