剑指Offer Java版 面试题21：调整数组顺序使奇数位于偶

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

参考答案

public class Solution {
    public void reOrderArray(int [] array) {
        if (array == null || array.length == 0) {
            return;
        }
        int begin = 0, end = array.length - 1;
        while (begin < end) {
            // 向后移动begin，直到它指向偶数
            while (begin < end && (array[begin] & 1) > 0) {
                begin++;
            }
            // 向前移动end，直到它指向奇数
            while (begin < end && (array[end] & 1) == 0) {
                end--;
            }
            if (begin < end) {
                int temp = array[begin];
                array[begin] = array[end];
                array[end] = temp;
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

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

练习地址

https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593

参考答案

public class Solution {
    public void reOrderArray(int [] array) {
        int n = array.length;
        int[] aux = new int[n];
        int i = 0;
        for (int j = 0; j < n; j++) {
            if ((array[j] & 1) == 1) {
                if (i != j) {
                    array[i] = array[j];
                }
                i++;
            } else {
                aux[j - i] = array[j];
            }
        }
        for (int j = i; j < n; j++) {
            array[j] = aux[j - i];
        }
    }
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题