本文轉載自【微信公眾號：五角錢的程式設計師，ID:xianglin965】經微信公眾號授權轉載，如需轉載與原文作者聯繫
21. 調整數組順序使奇數位於偶數前面
題目描述
需要保證奇數和奇數，偶數和偶數之間的相對位置不變，這和書本不太一樣。
解題思路
方法一：
創建一個新數組，時間複雜度 O(N)，空間複雜度 O(N)。
package 劍指offer.調整數組順序使奇數位於偶數前面_21;/*
作者 :XiangLin
文件 :OrderArray.java
IDE :IntelliJ IDEA
*/
import java.util.Arrays;
public class OrderArray {
public int[] reOrderArray(int[] nums){
//奇數個數
int oddCnt = 0;
for(int x: nums){
if (!isEven(x)){
oddCnt++;
}
}
int[] copy = nums.clone();
int i = 0, j = oddCnt;
for (int num : copy){
if (num % 2 == 1)
nums[i++] = num;
else
nums[j++] = num;
}
return nums;
}
private boolean isEven(int x){
return x % 2 == 0;
}
public static void main(String[] args) {
int nums[] = {1,2,3,4,5};
OrderArray o = new OrderArray();
int[] data = o.reOrderArray(nums);
System.out.println(Arrays.toString(data));
}
}
方法二：
使用冒泡思想，每次都將當前偶數上浮到當前最右邊。時間複雜度 O(N2)，空間複雜度 O(1)，時間換空間。
package 劍指offer.調整數組順序使奇數位於偶數前面_21;/*
作者 :XiangLin
文件 :OrderArray2.java
IDE :IntelliJ IDEA
*/
import java.util.Arrays;
public class OrderArray2 {
public int[] reOrderArray(int[] nums){
int N = nums.length;
for (int i = N - 1; i > 0; i --){
for (int j = 0; j < i; j++){
if (isEven(nums[i]) && !isEven(nums[j + 1])){
swap(nums,j,j+1);
}
}
}
return nums;
}
private boolean isEven(int x){
return x % 2 == 0;
}
private void swap(int[] nums, int i ,int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
public static void main(String[] args) {
int nums[] = {1,2,3,4,5};
OrderArray2 o = new OrderArray2();
int[] data = o.reOrderArray(nums);
System.out.println(Arrays.toString(data));
}
}