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

O(N), O(N)

只需要借助新数组，遍历两次，分别将奇数和偶数，添加即可

public class Solution {
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型一维数组
 */
public int[] reOrderArray (int[] array) {
    // write code here
    int[] res = new int[array.length];
    int idx = 0;
    
    for(int i = 0; i < array.length; i++){
        if(array[i] % 2 != 0){
            res[idx++] = array[i];
        }
    }
    
    for(int i = 0; i < array.length; i++){
        if(array[i] % 2 == 0){
            res[idx++] = array[i];
        }
    }
    
    return res;
}
}

O(N2), O(1)

参照 #调整数组顺序使奇数位于偶数前面(二)# 的双指针解法 https://blog.nowcoder.net/n/23814b2178764dd9a75e34dcde9b1494

（二）不要求相对顺序，（一）要求相对顺序，上一个解法是用空间换取了时间，接下的解法则是用时间换空间，思路同（二）双指针解法相似，可以发现，（二）中的解法只能保证奇数的相对顺序，却不能保证偶数的相对顺序，那么我们就要针对性的解决这一问题

[2,4,6,5,7]，以此为例子说明，当left指向2，i指向5，若是（二）中的解法，变换之后则是[5,4,6,2,7]，偶数相对位置发生变化，在（一）中，我们要使其成为[5,2,4,6,7]，则相当于从left至i-1依次向后移动一位，然后left处的位置用i的位置替换，详细见代码

public class Solution {
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型一维数组
 */
public int[] reOrderArray (int[] array) {//双指针
    // write code here
    int left = 0;
    for(int i = 0; i < array.length; i++){
        if(array[i] % 2 != 0){
            int tmp = array[i];
            for(int j = i; j > left; j--){
                array[j] = array[j - 1];
            }
            array[left++] = tmp;
        }
    }
    
    return array;
}
}