题目链接
题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
示例
输入:12345
输出:13524
解题思路
方法一: 创建一个新数组,时间复杂度 O(N),空间复杂度 O(N)。
public int[] reOrderArray (int[] array) {
int total = 0;
for(int i : array){
// 统计奇数的个数,作为偶数存放的起始索引
if (!isEven(i)) {
total++;
}
}
// 定义在新数组中奇数和偶数的起始索引,奇数起始索引为i,偶数起始索引为j
int i=0,j=total;
int[] newArray = new int[array.length];
for (int num : array){
//是奇数
if(!isEven(num)){
newArray[i++]=num;
}
//是偶数
else {
newArray[j++]=num;
}
}
return newArray;
}
public boolean isEven(int x){
if (x % 2 ==0) {
return true;
}
return false;
}
方法二:使用冒泡思想,每次都将当前偶数上浮到当前最右边。时间复杂度 O(N),空间复杂度 O(1),时间换空间。
public int[] reOrderArray2 (int[] array) {
for (int i=array.length-1;i>0;i--){
for(int j=0;j<i;j++){
if(isEven(array[j]) && !isEven(array[j+1])){
swap(array,j,j+1);
}
}
}
return array;
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
public boolean isEven(int x){
if (x % 2 ==0) {
return true;
}
return false;
}