[剑指 Offer 第 2 版第 21 题] “调整数组顺序使奇数位于偶数前面”做题记录

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

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

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

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

样例：

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

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

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

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

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

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++ 代码：

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--;
            }
        }
    }

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

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/