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

题目：

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

思路：

（摘抄剑指offer）维护两个指针：pBegin、pEnd。pBegin初始化时指向数组的第一个数字，它只向后移动；pEnd初始化时指向数组最后一个数字，它只能向前移动。
在两个指针相遇之前，第一个指针总是位于第二个指针的前面。
如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，就交换这两个数字。

解答：

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        //正常数组
        int[] arrays = new int[]{1, 2, 3, 4, 5, 6, 7};
        solution.reOrderArray(arrays);
        Arrays.stream(arrays).forEach(i -> System.out.print(i + "  "));
        System.out.println();

        //数组为空
       int[] arrays2 = null;
        solution.reOrderArray(arrays2);
        System.out.println();

        //数组只有一个数
        int[] arrays3 = new int[]{3};
        solution.reOrderArray(arrays3);
        Arrays.stream(arrays3).forEach(i->System.out.print(i + "  "));
        System.out.println();

    }
    /**
     * 重排数组
     * @param array
     */
    public void reOrderArray(int[] array) {
        if (array == null || array.length <= 0) {
            return;
        }
        //定义两个指针
        int pBegin = 0;
        int pEnd = array.length - 1;

        //当前指针与后指针没有相交
        while (pBegin < pEnd) {
            //当前指针遇到偶数停止
            while (pBegin < pEnd && !isEven(array[pBegin])) {
                pBegin++;
            }
            //当后指针遇到奇数停止
            while (pBegin < pEnd && isEven(array[pEnd])) {
                pEnd--;
            }
            //交换
            if (pBegin < pEnd) {
                swap(array, pBegin, pEnd);
            }

        }

    }

    /**
     * 两数交换
     *
     * @param array
     * @param pBegin
     * @param pEnd
     */
    private void swap(int[] array, int pBegin, int pEnd) {
        int temp = array[pBegin];
        array[pBegin] = array[pEnd];
        array[pEnd] = temp;
    }

    /**
     * 是否为偶数
     *
     * @param num
     * @return
     */
    private boolean isEven(int num) {
        return (num & 0x1) == 0;
    }
}

扩展

牛客上该题目有额外要求：并保证奇数和奇数，偶数和偶数之间的相对位置不变。
上面的解法就不再可行。所以只能采用前后值对比的形式。
定义两个指针（下标）：pBegin、pEnd。
外层遍历数组，当遇到偶数时，pBegin记录当前偶数下标，此时继续遍历数组直到遇到奇数pEnd。
那么[pBegin,pEnd)之间下标对应值都是偶数。此时将[pBegin,pEnd)对应值往后移动一位,p[pBegin]=array[pEnd]。这样就实现了奇数移到了偶数的前面。

解法：

package com.qingcong.system.codeGenerator;


import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        //正常数组
        int[] arrays = new int[]{1, 2, 3, 4, 5, 6, 7};
        solution.reOrderArray2(arrays);
        Arrays.stream(arrays).forEach(i -> System.out.print(i + "  "));
        System.out.println();

        //数组为空
       /* int[] arrays2 = null;
        solution.reOrderArray(arrays2);
        System.out.println();

        //数组只有一个数
        int[] arrays3 = new int[]{3};
        solution.reOrderArray(arrays3);
        Arrays.stream(arrays3).forEach(i->System.out.print(i + "  "));
        System.out.println();*/

    }

    /**
     * 重排数组
     * @param array
     */
    public void reOrderArray2(int[] array) {
        if (array == null || array.length <= 0) {
            return;
        }
        //指向第一个偶数
        int pBegin = 0;
        //指向第一个奇数
        int pEnd = 0;
        for (int i = 0; i < array.length; i++) {

            if (isEven(array[i])) {
                pBegin = i;
                pEnd = pBegin + 1;

                while (pEnd < array.length) {
                    if (!isEven(array[pEnd])) {
                        break;

                    }
                    pEnd++;
                }
                 //将array[pEnd]移到最前面，所有的偶数往后移
                if (pBegin != pEnd && pEnd < array.length) {
                    int temp = array[pEnd];
                    while (pEnd > pBegin) {
                        array[pEnd]  = array[--pEnd];
                    }
                    array[pBegin] = temp;
                }

            }
        }
    }

    /**
     * 是否为偶数
     *
     * @param num
     * @return
     */
    private boolean isEven(int num) {
        return (num & 0x1) == 0;
    }
}

扩展性

为什么需要单独实现个isEven方法？
如果题目要求的是能被3整除的移到前面，不能被整除的移到后面。或者是负数都要求在非负数前面。我们可以用一个函数来判断数字是否符合标准，在reOrderArray中被调用，而不再需要重写类似的reOrderArray函数。