题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
原地进行
采用类似插入排序的思想, k记录前面全是奇数的最后位置
- 搜寻到奇数
- 依次两两交换该奇数和前面的其他数 (这样的交换不会改变次序)
//空间O(1) 时间O(nlogn)? public class Solution { public void reOrderArray(int [] array) { int k = 0; int len = array.length; for(int i = 0; i < len; i++){ if(array[i] % 2 == 1){ int j = i; while(j > k){ int tmp = array[j]; array[j] = array[j - 1]; array[j - 1] = tmp; j--; } k++; } } } }
非原地进行
- 将奇数和偶数分别记录进一个新的数组
- 将这两个奇偶数组依次再填入旧数组(这里可以使用System.arraycopy())
public class Solution { public void reOrderArray(int [] array) { int[] a = new int[array.length]; int[] b = new int[array.length]; int j = 0; int k = 0; for(int num : array){ if(num % 2 == 0){ b[k++] = num; }else { a[j++] = num; } } for(int i = 0; i < j; i++){ array[i] = a[i]; } for(int i = 0; i < k; i++){ array[i + j] = b[i]; } } }