题解 | #调整数组顺序使奇数位于偶数前面#

思路一：不需要两个辅助数组，只需要一个辅助数组。正向遍历数组找奇数，从前往后放，反向遍历数组找偶数，从后往前放
时间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;
    }
}