描述

输入一个长度为 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
}

本文由 一切随风 创作,可自由转载、引用,但需署名作者且注明文章出处。

还不快抢沙发

添加新评论