Reorder Array with Odd Numbers Before Even Numbers

1. Problem Description

Given an integer array, implement a function that reorders its numbers so that all odd numbers are in the first half and all even numbers are in the second half, while preserving the relative order among odd numbers and among even numbers.

2. Approach

• Brute force: traverse the array and append odd numbers, then traverse it again and append even numbers
• Two pointers

3. Implementation

3.1. Brute Force

// Time: O(n)  Space: 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
}

// Time: O(n)  Space: 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. Two Pointers

The two-pointer implementation below does not preserve the relative order among odd numbers or among even numbers, so it only applies to versions that do not require stability.

// Time: O(n)
// Space: 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. References

• Reorder Array: Odd Numbers Before Even Numbers - NowCoder
• Sword Offer 21. Reorder Array: Odd Before Even - LeetCode
• LCR 139. Training Plan I - LeetCode