调整数组顺序使奇数位于偶数前面.md

题目描述

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

测试用例

• 功能测试（输入数组中的奇数、偶数交替出现；输入的数组中所有偶数都出现在奇数的前面；输入的数组所有奇数都出现在偶数的前面）
• 特殊输入测试（输入空指针；输入的数组只包含一个数字）

题目考点

• 考察应聘者的快速思维能力。
• 对于已经工作几年的应聘者，面试官还将考察其对扩展性的理解，要求应聘者写出的代码具有可重用性。

解题思路

只完成基本功能的解法

维护连个指针：第一个指针初始化时指向数组的第一个数字，它只向后移动；第二个指针指向数组的最后一个数字，它只向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，则交换这两个数字。

PS：为了避免重复交换，我们可以在可能交换之前，让两个指针分别向自己的方向扫描，直到第一个指针指向偶数，第二个指针指向奇数。

考虑可扩展的解法

这到题目是要求我们按照奇偶分类，如果我们要按照正负分类，我们第一反应应该是去该代码，但是这样很不好。耦合度太高，所以我们需要考虑扩展性。这里我们是可以使用 策略模式。

自己解题

/**
 * 调整数组顺序使奇数位于偶数前面
 * @Author rex
 * 2018/7/24
 */
public class Solution {
    /**
     * 调整数组顺序
     * @param array
     */
    public void reOrderArray(int [] array) {
        // 防止特殊输入
        if (array == null || array.length == 0) {
            return;
        }
        int i = 0;
        int j = array.length-1;
        while (j - i != 1) {
            if ((array[i] & 1) == 0) {
                // 为偶数
                swapArray(array, i, j);
                j--;
            } else {
                i++;
            }

        }
    }

    /**
     * 交换数组的两个值
     * @param array
     * @param i
     * @param j
     */
    public void swapArray(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}

考虑欠缺点：

多了很多没有必要的交换

参考解题

只完成基本功能的解法

/**
 * 调整数组顺序使奇数位于偶数前面
 * @Author rex
 * 2018/7/24
 */
public class Solution1 {
    /**
     * 只完成基本功能的解法
     * @param array
     */
    public void reOrderArray(int [] array) {
        // 防止特殊输入
        if (array == null || array.length == 0) {
            return;
        }
        int i = 0;
        int j = array.length-1;
        while (i < j) {
            // 第一个指针，直到遇见偶数，然后开始准备交换
            while (i < j && (array[i] & 1) != 0) {
                i++;
            }
            // 第二个指针，直到遇见奇数，然后开始准备交换
            while (i < j && (array[j] & 1) == 0) {
                j--;
            }
            // 开始交换
            if (i < j) {
                swapArray(array, i, j);
            }
        }
    }

    /**
     * 交换数组的两个值
     * @param array
     * @param i
     * @param j
     */
    public void swapArray(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}

考虑可扩展的解法

/**
 * 重排序策略
 * @Author rex
 * 2018/7/25
 */
public interface ReorderStrategy {
    /**
     * 判断符合某种条件
     * @param array
     * @param index
     */
    boolean reorderBySomething(int[] array, int index);
}

/**
 * 按照奇偶重排序
 * @Author rex
 * 2018/7/25
 */
public class OddEventReorderStategy implements ReorderStrategy {
    /**
     * 返回是否为偶数
     * @param array
     * @param index
     * @return
     */
    @Override
    public boolean reorderBySomething(int[] array, int index) {
        return (array[index] & 1) == 0;
    }
}

/**
 * @Author rex
 * 2018/7/25
 */
public class Solution2 {
    /**
     * 判断的策略
     */
    private ReorderStrategy reorderStrategy;

    public Solution2() {
    }

    public Solution2(ReorderStrategy reorderStrategy) {
        this.reorderStrategy = reorderStrategy;
    }

    /**
     * 只完成基本功能的解法
     * @param array
     */
    public void reOrderArray(int [] array) {
        // 防止特殊输入
        if (array == null || array.length == 0) {
            return;
        }
        int i = 0;
        int j = array.length-1;
        while (i < j) {
            // 第一个指针，直到遇见偶数，然后开始准备交换
            while (i < j && !reorderStrategy.reorderBySomething(array, i)) {
                i++;
            }
            // 第二个指针，直到遇见奇数，然后开始准备交换
            while (i < j && reorderStrategy.reorderBySomething(array, j)) {
                j--;
            }
            // 开始交换
            if (i < j) {
                swapArray(array, i, j);
            }
        }
    }

    /**
     * 交换数组的两个值
     * @param array
     * @param i
     * @param j
     */
    public void swapArray(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        int[] array = new int[] {2,4,4,6,8,10,1,3,5};
        ReorderStrategy reorderStrategy = new OddEventReorderStategy();
        Solution2 solution = new Solution2(reorderStrategy);
        solution.reOrderArray(array);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}

补充

策略模式：设计模式之禅——策略模式