剑指offer最优解Java版-调整数组顺序使奇数位于偶数前面

题目描述

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

第一种方案

对于每一位数字进行类似冒泡的算法，将其挪至数组开头

public class Solution {
    public void reOrderArray(int[] array) {
        int length = array.length;
        if (length <= 1) {
            return;
        }
        for (int i = 0; i < array.length; i++) {
            for (int j = array.length - 1; j > i; j--) {
                if (array[j] % 2 != 0 && array[j - 1] % 2 == 0) {
                    swap(array, j - 1, j);
                }
            }
        }

    }

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

复杂度分析：

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

第二种方案：空间换时间

新建数组，将奇数偶数存到两个数组中，然后再分别写回结果数组中。

public class Solution {
    public void reOrderArray(int[] array) {
        int length = array.length;
        if (length <= 1) {
            return;
        }
        List<Integer> odds = new ArrayList<>();
        List<Integer> evens = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 0) {
                evens.add(array[i]);
            } else {
                odds.add(array[i]);
            }
        }
        for (int i = 0; i < odds.size(); i++) {
            array[i] = odds.get(i);
        }
        for (int i = 0; i < evens.size(); i++) {
            array[i + odds.size()] = evens.get(i);
        }
    }
}

复杂度分析：

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

哎呀，如果我的名片丢了。微信搜索“全菜工程师小辉”，依然可以找到我