劍指offer專題地址

劍指offer索引地址

題目描述

輸入一個整數(shù)數(shù)組，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對位置不變。

第一種方案

對于每一位數(shù)字進(jìn)行類似冒泡的算法，將其挪至數(shù)組開頭

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;
    }
}

復(fù)雜度分析：

• 時間復(fù)雜度：O(n²)。
• 空間復(fù)雜度：O(1)。

第二種方案：空間換時間

新建數(shù)組，將奇數(shù)偶數(shù)存到兩個數(shù)組中，然后再分別寫回結(jié)果數(shù)組中。

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);
        }
    }
}

復(fù)雜度分析：

• 時間復(fù)雜度：O(n)。
• 空間復(fù)雜度：O(n)。

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