题目主要信息

输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。

方法一：复制

具体方法

先遍历数组array找到其中的奇数有多少个，然后准备两个起始坐标，x表示奇数的起始坐标从0开始，y表示偶数的起始坐标，从刚刚找到的奇数个数开始，然后遍历数组array，将所有的元素复制到待返回的数组中，遇到奇数我们用下标x，遇到偶数我们用下标y。

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArrayTwo (int[] array) {
        // write code here
        int n = array.length;
        int []result = new int[n];
        int count = 0; //统计奇数个数
        for(int i = 0; i < n; i++){ //遍历统计
            if(array[i] % 2 == 1)
                count++;
        }
        int x = 0, y = count; //x与y分别表示答案中奇偶数的坐标
        for(int i = 0; i < n; i++){
            if(array[i] % 2 == 1){ //奇数在前
                result[x] = array[i];
                x++;
            }else{ //偶数在后
                result[y] = array[i];
                y++;
            }
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，其中n为数组的长度，遍历2次数组
• 空间复杂度：$O(n)O(n)$，result数组属于返回函数

方法二：双指针

具体方法

• 首尾双指针 定义头指针 left，尾指针 right .
• left 一直往右移，直到它指向的值为偶数
• right 一直往左移， 直到它指向的值为奇数
• 交换 nums[left] 和 nums[right]n. 重复上述操作，直到 left == right.

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArrayTwo (int[] array) {
        // write code here
        int left = 0, right = array.length - 1;
        while (left < right) {
            if ((array[left] & 1) != 0) {
                left ++;
                continue;
            }
            if ((array[right] & 1) != 1) {
                right --;
                continue;
            }
             int temp = array[left];
             array[left] = array[right];
             array[right] = temp;
            left++;
            right--;
        }
        return array;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$,遍历数组一次
• 空间复杂度：$O(1)O(1)$，一个交换数组值的temp