输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
拿到题目我首先想到可以类比C++在头尾处放两个指针,左指针指向奇数指针右移,右指针指向偶数指针左移,否则指针不动,等到左指针指向偶数且右指针指向奇数,这时直接调换左右顺序即可。这样时间复杂度O(n),空间复杂度O(1)。但是题目要求奇数偶数相对位置不能改变,这个方法就无效了。
方法1 临时数组法
接下来切换思路,我的想法是扫描两边数组,分别将奇数和偶数存放在两个临时数组中,这样其相对位置不会发生改变,在扫描存放奇数的数组,一旦发现空位就将偶数数组复制进去,这样能保证时间复杂度仍为O(n),而空间复杂度也为O(n)。
时间复杂度O(n)
空间复杂度O(n)
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param array int整型一维数组 * @return int整型一维数组 */ public int[] reOrderArray (int[] array) { // write code here int[] temp1 = new int[array.length]; int[] temp2 = new int[array.length]; int i=0; int j=0; int k=0; int m=0; int n=0; while(i<array.length){ if(array[i]%2 == 1){ temp1[j] = array[i]; j++; } if(array[i]%2 == 0){ temp2[k] = array[i]; k++; } i++; } for(m=0; m<array.length&&temp1[m]%2==1; m++); for(n=m; n<array.length; n++){ temp1[n] = temp2[n-m]; } return temp1; } }
方法2 冒泡排序
后来我又想到可以利用冒泡排序的思想,找到奇数就放到前面,最后结果也是一样的。这里就不付代码了。
时间复杂度O(n^2)
空间复杂度O(1)