12. 调整数组顺序使奇数位于偶数前面 --剑指Offer(java版)
github地址题目描述输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。最暴力的解法: 新写一个数组,遍历一遍原数组将奇数放入头部,偶数放入尾部。O(n),O(n)/*** 使用两个数组,* 从前遍历旧数组找到所有的奇数并...
·
题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
最暴力的解法: 新写一个数组,遍历一遍原数组将奇数放入头部,偶数放入尾部。O(n),O(n)
/**
* 使用两个数组,
* 从前遍历旧数组找到所有的奇数并放入新数组,
* 从前遍历旧数组找到所有的奇数并放入新数组。
* 空间O(n),时间O(n)
*/
public void reOrderArray(int[] array) {
// solutionBySort(array);
// 双数组
// copy原数组顺序
int[] copy = new int[array.length];
System.arraycopy(array, 0, copy, 0, array.length);
// 从前到后遍历找到所有奇数,放入结果数组中
int j = 0;
for (int i = 0; i < array.length; i++) {
if (copy[i] % 2 == 1) {
array[j++] = copy[i];
}
}
// 从前到后遍历找到所有偶数,放入结果数组中
for (int i = 0; i < array.length; i++) {
if (copy[i] % 2 == 0) {
array[j++] = copy[i];
}
}
// 上述两步可以合并为一步,但是我懒。
}
其实这道题对java使用者来说简单,因为Java中的Arrays.sort()是基于归并排序的,(稳定的排序,但是需要O(n)的空间),而C++中的是sort()和qsort()是不稳定的(O(1)空间),所以Java这题可以直接实现Comparator接口,当然空间O(1),时间O(n*log n).
/**
* 使用Java自带的比较器功能
* 时间O(n*log(n))-->双轴排序,空间O(1)
*/
private void solutionBySort(int[] array) {
Integer[] a = new Integer[array.length];
for (int i = 0; i < array.length; i++) {
a[i] = array[i];
}
Arrays.sort(a, new Comp());
for (int i = 0; i < array.length; i++) {
array[i] = a[i];
}
}
/**
* 自定义比较器,奇数比偶数小。
*/
class Comp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
if (o1 % 2 == o2 % 2) {
return 0;
} else if (o1 % 2 == 0 && o2 % 2 == 1) {
return 1;
} else {
return -1;
}
}
}
如果不想使用任何辅助空间,可以使用插入排序,时间复杂度:O(n^2).
/**
* 通过插入排序实现,不使用额外内存空间,但是时间效率较低:O(n^2)
*
* @param arr
*/
private void solutionByInsertSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] % 2 == 0) {
// 偶数不动
} else {
// 奇数向前走,走到前面的元素不是偶数未知
for (int j = i; j >= 1 && arr[j - 1] % 2 == 0; j--) {
swap(arr, j, j - 1);
}
}
}
System.out.println(Arrays.toString(arr));
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
已为社区贡献2条内容
所有评论(0)