描述

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

数据范围：0≤n≤50000，数组中每个数的值 0≤val≤10000

要求：时间复杂度 O(n)，空间复杂度 O(1)

示例

// 输入
[1,2,3,4]
// 输出
[1,3,2,4]
// 说明
[3,1,2,4]或者[3,1,4,2]也是正确答案 

// 输入
[1,3,5,6,7]
// 输出
[1,3,5,7,6]
// 说明
[3,1,5,7,6]等也是正确答案 

// 输入
[1,4,4,3]
// 输出
[1,3,4,4]

代码实现

遍历数组，将奇数添加到新数组头部，偶数 append 到数组尾部

/**
 * [JZ81-简单] 调整数组顺序使奇数位于偶数前面(二)
 *
 * @param array int 整型一维数组
 * @return int 整型一维数组
 */
func reOrderArrayTwo(array []int) []int {
    n := len(array)
    if n <= 1 {
        return array
    }

    var arr []int
    for _, v := range array {
        if v%2 == 1 {
            arr = append([]int{v}, arr...)
        } else {
            arr = append(arr, v)
        }
    }
    return arr
}

双指针（优化）

• 先遍历数组获取奇数个数 odd，也就是偶数在新数组起点位置
• 双指针 left、right，奇数在 0 位置后添加，偶数在 odd 位置后添加

/**
 * [JZ81-简单] 调整数组顺序使奇数位于偶数前面(二)
 *
 * @param array int 整型一维数组
 * @return int 整型一维数组
 */
func reOrderArrayTwo2(array []int) []int {
    n := len(array)
    if n <= 1 {
        return array
    }

    odd := 0
    for _, v := range array {
        if v%2 == 1 {
            odd++
        }
    }

    left, right := 0, odd
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        if array[i]%2 == 1 {
            arr[left] = array[i]
            left++
        } else {
            arr[right] = array[i]
            right++
        }
    }
    return arr
}