《剑指 Offer （第 2 版）》第 21 题：调整数组使得奇

第 21 题：调整数组使得奇数位于偶数之前

传送门：AcWing：调整数组顺序使奇数位于偶数前面，牛客网 online judge 地址。

输入一个整数数组，实现一个函数来调整该数组中数字的顺序。

使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

样例：

输入：[1,2,3,4,5]

输出： [1,3,5,2,4]

分析：这道题要注意的一点就是：保持原来的顺序，具体可以参考 LeetCode 第 88 题的策略，从后向前重新为数组赋值。

思路1：有点类似“两路快排”的思路。“两路快排”中有一些细节需要复习一下。双指针扫描：用两个指针分别从首尾开始，往中间扫描。扫描时保证第一个指针前面的数都是奇数，第二个指针后面的数都是偶数。每次迭代时需要进行的操作：

1、第一个指针一直往后走，直到遇到第一个偶数为止；
2、第二个指针一直往前走，直到遇到第一个奇数为止。
交换两个指针指向的位置上的数，再进入下一层迭代，直到两个指针相遇为止。
时间复杂度：当两个指针相遇时，走过的总路程长度是 ，所以时间复杂度是 。

Python 代码：

class Solution(object):
    def reOrderArray(self, array):
        """
        :type array: List[int]
        :rtype: void
        """
        # 特判
        size = len(array)
        if size < 2:
            return

        l = 0
        r = size - 1

        # 始终保持 [0,l) 是奇数
        # (r,size-1] 是偶数
        
        while True:
            while l <= r and array[l] & 1 == 1:
                l += 1
            # 此时 l 来到了第一个偶数位置
            while r >= l and array[r] & 1 == 0:
                r -= 1
            # 此时 r 来到了第一个奇数的位置
            
            # 这里一定是大于号，否则数组下标会越界
            # 一定要特别注意，写 == 号会出错，写 >= 是可以的，因为 == 成立的时候，不用交换
            if l > r:
                break
            array[l], array[r] = array[r], array[l]
            l += 1
            r -= 1
        return array

C++ 代码：

image-20190108005607547

C++ 代码：

class Solution {
public:
    void reOrderArray(vector<int> &array) {
         int l = 0, r = array.size() - 1;
         while (l <= r) {
             while (array[l] % 2 == 1) l ++ ;
             while (array[r] % 2 == 0) r -- ;
             if (l < r) swap(array[l], array[r]);
         }
    }
};

思路2：把奇数数组复制出来，按照从后向前归并排序的做法完成。

Java 代码：

import java.util.Arrays;

public class Solution {
    // 保证奇数和奇数，偶数和偶数之间的相对位置不变。
    public void reOrderArray(int[] array) {
        int len = array.length;
        if (len == 0) {
            return;
        }
        // 奇数全部挪到缓存数组中
        int[] buff = new int[len];
        int j = -1;
        for (int i = 0; i < len; i++) {
            if (array[i] % 2 == 1) {
                j++;
                buff[j] = array[i];
            }
        }
        // 如果都没有奇数的话，程序终止
        if (j == -1) {
            return;
        }
        // 把偶数集中“挤”到数组的末尾
        // 然后再把缓存数组中的奇数倒序放入
        int k = len - 1;
        for (int i = len - 1; i >= 0; i--) {
            if (array[i] % 2 == 0) {
                array[k] = array[i];
                k--;
            }
        }
        while (j >= 0) {
            array[j] = buff[j];
            j--;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        Solution solution = new Solution();
        solution.reOrderArray(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Java 代码：

import java.util.Arrays;

public class Solution {
    // 保证奇数和奇数，偶数和偶数之间的相对位置不变。
    public void reOrderArray(int[] array) {
        int len = array.length;
        if (len == 0) {
            return;
        }
        // 奇数全部挪到缓存数组中
        int[] buff = new int[len];
        int j = -1;
        for (int i = 0; i < len; i++) {
            if (array[i] % 2 == 1) {
                j++;
                buff[j] = array[i];
            }
        }
        // 如果没有奇数，直接返回就可以了
        if (j == -1) {
            return;
        }
        // 从后向前赋值
        int k = len - 1;
        for (int i = len - 1; i >= 0; i--) {
            if (array[i] % 2 == 0) {
                array[k] = array[i];
                k--;
            }
        }
        while (j >= 0) {
            array[j] = buff[j];
            j--;
        }
    }
}

扩展：书本上有这个问题更一般的做法。