题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
代码示例
import java.util.Arrays;
public class Offer14 {
public static void main(String[] args) {
int[] nums = {2,1,3,5,4};
Offer14 testObj = new Offer14();
testObj.reOrderArray(nums);
// testObj.reOrderArray2(nums);
System.out.println(Arrays.toString(nums));
}
//法1:使用额外的数组
public void reOrderArray(int[] nums) {
//奇数个数
int oddCnt = 0;
for (int x : nums) {
if (x % 2 == 1) {
oddCnt++;
}
}
int[] clone = nums.clone();
int i = 0;
int j = oddCnt;
for (int num : clone) {
//[0, oddCnt)的索引存放奇数
if (num % 2 == 1) {
nums[i++] = num;
} else {
nums[j++] = num;
}
}
}
//法2:通过冒泡的方式上浮到最右端
public void reOrderArray2(int[] nums) {
int length = nums.length;
//执行length-1次,每次将一个偶数上浮到最右边
for (int i = length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (nums[j] % 2 == 0 && nums[j+1] % 2 == 1) {
swap(nums, j, j+1);
}
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}