面试 6：调整数组顺序使奇数位于偶数前面

今天给大家带来的是 《剑指 Offer》习题：调整数组顺序使奇数位于偶数前面，纯 Java 实现希望大家多加思考。

面试题：输入一个整型数组，实现一个函数来调整该数组中的数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分，希望时间复杂度尽量小。

看到这道题，想必大多数人都是能一下就想到从头到尾扫描一遍数组，然后遇到奇数就移动到最前面，遇到偶数就移动到最后面的思路，于是便有了下面的代码。

注：《剑指 Offer》上面的 「遇到奇数移动到最前面，遇到偶数也移动到最后面」其实只需要做其中一种即可。

public class Test14 {

    private static int[] reOrderArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 遇到奇数就放到最前面
            if (Math.abs(arr[i]) % 2 == 1) {
                int temp = arr[i];
                // 先把 i 前面的都向后移动一个位置
                for (int j = i; j > 0; j--) {
                    arr[j] = arr[j - 1];
                }
                arr[0] = temp;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        arr = reOrderArray(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();

        int[] arr1 = {2, 4, 6, 8, 1, 3, 5, 7, 9};
        arr1 = reOrderArray(arr1);
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i] + " ");
        }
        System.out.println();

        int[] arr2 = {2, 4, 6, 8, 10};
        arr2 = reOrderArray(arr2);
        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i] + " ");
        }
    }
}

上面的代码固然能达到功能，但时间复杂度上完全不能恭维。每找到一个奇数，我们总是要去移动不少个位置的数。

等等。

我们上面算法最大的问题在于移动，我们能否不做这个移动呢？

当然是可以的。题目要求所有奇数都应该在偶数前面，所以我们应该只需要维护两个下标值，让一个下标值从前往后遍历，另外一个下标值从后往前遍历，当发现第一个下标值对应到偶数，第二个下标值对应到奇数的时候，我们就直接对调两个值。直到第一个下标到了第二个下标的后面的时候退出循环。

我们有了这样的想法，可以先拿一个例子在心中走一遍，如果没有问题再写代码，这样也可以让面试官知道，我们并不是那种上来就开始写代码不考虑全面的程序员。

1. 假定输入的数组是 {1，2，3，4，5}；
2. 设定 odd = 0，代表第一个下标；even = arr.length = 4；
3. 从前往后移动第一个下标 odd，直到它等于偶数，即当 odd = 1 的时候，我们停止移动；
4. 再从后往前移动下标 even，直到它等于奇数，即当 even = 4 的时候，我们停止移动；
5. 满足 arr[odd] 为偶数，arr[even] 为奇数，我们对调两个值，得到新数组 {1，5，3，4，2}；
6. 继续循环，此时 odd = 3,even = 2，不满足 odd < even 的条件，退出循环，得到的数组符合条件；

心中默走一遍没问题后，开始手写代码：

public class Test14 {

    private static int[] reOrderArray(int[] arr) {
        int odd = 0, even = arr.length - 1;
        // 循环结束条件为 odd >= even
        while (odd < even) {
            // 第一个下标为偶数的时候停止
            while (odd < even && Math.abs(arr[odd]) % 2 != 0) {
                odd++;
            }
            // 第二个下标为奇数的时候停止
            while (odd < even && Math.abs(arr[even]) % 2 == 0) {
                even--;
            }

            // 找到后对调两个值
            int temp = arr[odd];
            arr[odd] = arr[even];
            arr[even] = temp;

        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        arr = reOrderArray(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();

        int[] arr1 = {2, 4, 6, 8, 1, 3, 5, 7, 9};
        arr1 = reOrderArray(arr1);
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i] + " ");
        }
        System.out.println();

        int[] arr2 = {2, 4, 6, 8, 10};
        arr2 = reOrderArray(arr2);
        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i] + " ");
        }
        System.out.println();
    }
}

扩展性更好的代码，能秒杀 Offer

如果是面试应届毕业生或者工作时间不长的程序员，面试官可能会满意前面的代码，但如果应聘者申请的是资深 的开发岗位，那面试官可能会接着问几个问题。

• 面试官：如果把题目改成把数组中的数组按照大小分为两部分，所有的负数都在非负整数的前面，该怎么做？
• 应聘者：这很简单，可以重新定义一个函数，在新的函数里，只要修改第二个和第三个 while 循环里面的判断条件就好了。
• 面试官：如果再把题目改改，变成把数组中的数分为两部分，能被 3 整除的数都在不能被 3 整除的数的前面，怎么办？
• 应聘者：我们还是可以定义一个新的函数，在这个函数中......
• 面试官：(打断应聘者的话)，难道就没有更好的方法？

这个时候应聘者应该要反应过来，面试官期待我们能提供的不仅仅是解决一个问题的办法，而是解决一系列同类型问题的通用方法。我们在做解法的时候不能只想着解决当前的问题就好。在《大话设计模式》中，讲解了一个非常有意思的事情就是大鸟让小菜做商场促销活动的时候，各种改变需求，把小菜绕的云里雾里。

《大话设计模式》PDF 版本可以在公众号后台回复「大话设计模式」即可获取。

是呀，哪有不变的需求，需求不变，我们哪来那么多活干呀？不过要是，我们事先就做了这样的准备，省下来的时间那不是正好又可以去玩一盘吃鸡洛？

回到面试官新提出的两个问题来，我们其实新的函数都只需要更改第二个和第三个 while 循环里面的判断条件，而其它都是不需要动的。

public class Test14 {

    interface ICheck {
        boolean function(int n);
    }

    public static class OrderEven implements ICheck {
        @Override
        public boolean function(int n) {
            return n % 2 == 0;
        }
    }

    private static int[] reOrderArray(int[] arr, ICheck iCheck) {
        int odd = 0, even = arr.length - 1;
        // 循环结束条件为 odd >= even
        while (odd < even) {
            // 第一个下标为偶数的时候停止
            while (odd < even && !iCheck.function(arr[odd])) {
                odd++;
            }
            // 第二个下标为奇数的时候停止
            while (odd < even && iCheck.function(arr[even])) {
                even--;
            }

            // 找到后对调两个值
            int temp = arr[odd];
            arr[odd] = arr[even];
            arr[even] = temp;

        }
        return arr;
    }

    public static void main(String[] args) {
        OrderEven even = new OrderEven();
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        arr = reOrderArray(arr,even);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();

        int[] arr1 = {2, 4, 6, 8, 1, 3, 5, 7, 9};
        arr1 = reOrderArray(arr1,even);
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i] + " ");
        }
        System.out.println();

        int[] arr2 = {2, 4, 6, 8, 10};
        arr2 = reOrderArray(arr2,even);
        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i] + " ");
        }
        System.out.println();

    }
}

写这玩意儿的时候，我内心是拒绝的，由于 Java 没有 Python 一样方便的函数指针，我想了想只想到了用接口方式来处理。要是有其他实现方式的希望大家能在评论区留言~

好了，今天的面试讲解，就先到这儿吧。