调整数组顺序使奇数位于偶数前面

1. 题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

2. 思路

• 暴力法：遍历数组，把奇数加入；再遍历数组，把偶数加入
• 双指针

3. 实现

3.1. 暴力法

// 时间：O(n)  空间：O(n)
func ReOrderArray(array []int) []int {
	if len(array) == 0 {
		return array
	}

	res := make([]int, 0)

	oushu := make([]int, 0)
	jishu := make([]int, 0)

	for _, val := range array {
		if val%2 == 0 {
			oushu = append(oushu, val)
			continue
		}

		jishu = append(jishu, val)
	}

	res = append(res, jishu...)
	res = append(res, oushu...)

	return res
}

// 时间：O(n)  空间：O(n)
func ReOrderArray2(array []int) []int {
	if len(array) == 0 {
		return array
	}

	res := make([]int, 0)

	for _, val := range array {
		if val%2 == 1 {
			res = append(res, val)
		}
	}
	for _, val := range array {
		if val%2 == 0 {
			res = append(res, val)
		}
	}

	return res
}

3.2. 双指针

下面的双指针写法不保证奇数、偶数各自的相对顺序，只适用于不要求稳定性的版本。

// 时间：O(n)
// 空间：O(1)
func ReOrderArray3(array []int) []int {
	if len(array) == 0 {
		return nil
	}

	left := 0
	right := len(array) - 1
	for left < right {
		for left < right && array[left]%2 == 1 {
			left++
		}
		for left < right && array[right]%2 == 0 {
			right--
		}
		array[left], array[right] = array[right], array[left]
		left++
		right--
	}

	return array

}

func exchange(nums []int) []int {
    left := 0
    right := len(nums)-1
    for left < right {
        for left < right && nums[left] % 2 == 1 {
            left++
        }
        for left < right && nums[right] % 2 == 0 {
            right--
        }
        nums[left],nums[right] = nums[right],nums[left]
    }
    return nums
}

4. 参考

• 调整数组顺序使奇数位于偶数前面_牛客网
• 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode）
• LCR 139. 训练计划 I - 力扣（LeetCode）