题解 | #调整数组顺序使奇数位于偶数前面#
调整数组顺序使奇数位于偶数前面
http://www.nowcoder.com/practice/ef1f53ef31ca408cada5093c8780f44b
思路一:不需要两个辅助数组,只需要一个辅助数组。正向遍历数组找奇数,从前往后放,反向遍历数组找偶数,从后往前放
时间2*N 即O(N),空间O(N)
import java.util.*; public class Solution { public int[] reOrderArray (int[] array) { // write code here int arrs[]=new int[array.length]; int j=0; for(int i=0;i<array.length;i++)//遍历奇数放到数组的前半部分,从前往后放 { if((array[i]&1)==1) arrs[j++]=array[i]; } j=array.length-1; for(int i=array.length-1;i>=0;i--)//遍历偶数放到数组的后半部分,从后往前放 { if((array[i]&1)==0) arrs[j--]=array[i]; } return arrs; } }
思路二:双指针,原数组进行交换,时间换空间
指针i指向非奇数,指针j指向奇数,假设当前不存在奇数,则i指向索引0,j也指向索引0,j遍历数组找到奇数。临时变量temp存放当前奇数,再将当前奇数索引j-1到i依次后移,而i腾出的位置即为奇数所要存放的位置。实际上我们是在偶数里面挑奇数,然后偶数顺延。直到把所有奇数都挑出来,这样就达到不改变相对位置的目的
复杂度:遍历数组为O(N),每次数组后移为O(N),所以时间为N^2,原地交换空间为O(1)
import java.util.*; public class Solution { public int[] reOrderArray (int[] array) { // write code here int i=0; for(int j=0;j<array.length;j++) { if((array[j]&1)==1) { int temp=array[j]; for(int k=j-1;k>=i;k--) { array[k+1]=array[k]; } array[i++]=temp; } } return array; } }