OfferJZ21 adjusts the array order so that the odd number precedes the even number

“This is the 14th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

1. Title Description

Take an array of integers of length n, implement a function to adjust the order of the numbers in the array, such that all odd numbers are in the first part of the array, all even numbers are in the last part of the array, and ensure that the relative positions between odd and odd numbers, and even and even numbers remain the same.

Data range: 0≤ N ≤5000, the value of each number in the array 0≤val≤10000

Requirements: Time complexity O(n), space complexity O(n)

Advanced: time complexity O(n^2), space complexity O(1)

Second, the problem solving

This problem requires us to adjust the order of the array to odd after the first even disaster while keeping the relative position between odd and even unchanged.

At the same time, two different time and space requirements are given, so we adopt two different methods to solve the problem.

① Cache array method

Given space complexity O(n), we can open two arrays to cache odd and even numbers respectively.

The array is iterated once, putting the odd numbers into cache array 1 and the even numbers into cache array 2.

When the loop is complete, concatenate the two arrays so that array 1 comes first and array 2 comes last.

func reOrderArray( array []int ) []int {
    // write code here
    var array1, array2 []int
    for _, num := range array {
        if num % 2= =0 {
            array2 = append(array2, num)
        } else {
            array1 = append(array1, num)
        }
    }
    return append(array1, array2...)
}
Copy the code

Bubble insertion method

When the space complexity requirement is O(1), we have to consider adjusting on the original array.

If they don’t want parity to be the same relative to each other, then you can do it in O(n) time by traversing, by switching between odd and even to make sure that the odd is always in front of the even. However, this method does not guarantee relative position stability and therefore cannot be used.

To ensure the relative position stability, simple exchange is not possible. However, by inserting odd numbers before even numbers, the relative positions can not be damaged. For arrays, in-situ insertion takes O(n) time complexity cost. In other scenarios, lists can be used instead.

In implementation, we can simulate bubble sort by:

func reOrderArray( array []int ) []int {
    // write code here
    for i := 0; i < len(array); i++ {
        // Find even numbers
        if array[i] % 2= =0 {
            for j := i + 1; j < len(array); j++ {
                // Look for odd numbers after even numbers
                if array[j] % 2= =1 {
                    // Cache odd numbers
                    odd := array[j]
                    for k := j; k > i; k-- {
                        // Move the interval one bit later
                        array[k] = array[k - 1]}// Insert odd numbers
                    array[i] = odd
                    // Complete the insertion
                    break}}}}return array
}
Copy the code