【算法】奇数位于偶数前面

剑指 Offer 第 21 题-奇数位于偶数前面

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

描述

输入一个长度为 n 整数数组，数组里面不含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

数据范围：0 <= n <= 50000，数组中每个数的值 0 <= val <= 100000

要求：时间复杂度 O(n)O(n)，空间复杂度 O(n)O(n)

进阶：时间复杂度 O(n^2)O(n )，空间复杂度 O(1)O(1)

方法 1 - 枚举法

创建一个新的数组，分两次遍历数组并添加到新数组中。

public class Jz21_1 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(reOrderArray(new int[]{1, 2, 3, 4})));
        System.out.println(Arrays.toString(reOrderArray(new int[]{2, 4, 6, 5, 7})));
    }

    public static int[] reOrderArray(int[] array) {
        int[] result = new int[array.length];

        int index = 0;
        for (int odd : array) {
            if (odd % 2 == 1) {
                result[index++] = odd;
            }
        }
        for (int even : array) {
            if (even % 2 == 0) {
                result[index++] = even;
            }
        }
        return result;
    }
}

方法 2 - 冒泡法

找到下一个奇数位置，冒泡到前面来

public class Jz21_2 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(reOrderArray(new int[]{2, 4, 6, 5, 7})));
    }

    public static int[] reOrderArray(int[] array) {

        for (int i = 0; i < array.length; i++) {

            // 当前位置是否是奇数
            final boolean odd = array[i] % 2 == 1;

            // 当前位置是奇数，进入下一轮
            if (odd) {
                continue;
            }

            // 下一个奇数位置
            int nextOddIndex = -1;

            // 当前是偶数
            // 找到下一个奇数位置
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] % 2 == 1) {
                    nextOddIndex = j;
                    break;
                }
            }
            // 如果后面没有奇数了，可以直接退出了
            if (nextOddIndex == -1) {
                return array;
            }

            // 存在奇数，下一个奇数冒泡到当前偶数所在的位置
            bubble(array, i, nextOddIndex);

        }
        return array;
    }

    private static void bubble(int[] array, int currentIndex, int nextOddIndex) {
        while (currentIndex < nextOddIndex) {
            swap(array, nextOddIndex - 1, nextOddIndex);
            nextOddIndex = nextOddIndex - 1;
        }
    }

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

策略化版本

输入一个长度为 n 整数数组，数组里面不含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分
（注意，区别于前面的版本，这里不需要保证奇数和奇数，偶数和偶数之间的相对位置不变。）

另外添加了其它的策略：偶数在前、能被 3 整除的在前。

这个做法，能够灵活适配新的类似的要求。

public class Jz21_3 {
    public static void main(String[] args) {
        System.out.println("奇数排在前面");
        System.out.println(Arrays.toString(reOrderArray(new int[]{2, 4, 6, 5, 7}, Jz21_3::isOdd)));
        System.out.println(Arrays.toString(reOrderArray(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, Jz21_3::isOdd)));

        System.out.println("偶数排在前面");
        System.out.println(Arrays.toString(reOrderArray(new int[]{2, 4, 6, 5, 7}, Jz21_3::isEven)));
        System.out.println(Arrays.toString(reOrderArray(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, Jz21_3::isEven)));

        System.out.println("能被3整除的在前面");
        System.out.println(Arrays.toString(reOrderArray(new int[]{2, 4, 6, 5, 7}, Jz21_3::isThreeTime)));
        System.out.println(Arrays.toString(reOrderArray(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, Jz21_3::isThreeTime)));
    }

    public static int[] reOrderArray(int[] array, Predicate<Integer> predicate) {

        if (array == null || array.length == 0) {
            return array;
        }

        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            while (left < right && predicate.test(array[left])) {
                left++;
            }

            while (left < right && !predicate.test(array[right])) {
                right--;
            }
            if (left < right) {
                swap(array, left, right);
            }
        }
        return array;
    }

    private static boolean isOdd(int i) {
        return i % 2 == 1;
    }

    private static boolean isEven(int i) {
        return i % 2 == 0;
    }

    private static boolean isThreeTime(int i) {
        return i % 3 == 0;
    }


    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];

        array[j] = tmp;
    }
}