题目描述

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

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

样例

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

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

算法

(双指针扫描) $O(n)$

两个指针 l、r，l 从前往后扫描，r 从后往前后扫描

1. l < r 且 l 指针遇到偶数就停下
2. l < r 且 r 指针遇到奇数就停下
3. l < r 交换两个数

时间复杂度

两个指针总共走的路程为 n，所以时间复杂度是 $O(n)$

C++ 代码

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