描述

题目描述

首先给定我们一个数组, 让我们把奇数放到前面, 然后偶数放到后面, 最后返回我们的这个操作之后的数组

题解

解法一:

实现思路

这个我们可以直接暴力遍历我们的数组两次, 第一次把我们的奇数存入数组, 第二次我们把我们的偶数存入我们的数组, 然后我们返回我们的这个数组即可

代码实现

class Solution {
   public:
    vector<int> reOrderArrayTwo(vector<int>& array) {
        vector<int> res;
        for (auto &it : array) if (it & 1) res.emplace_back(it);
        // 第一次把奇数的放入我们的答案数组
        for (auto &it : array) if (!(it & 1)) res.emplace_back(it);
        // 第二次把我们的偶数放入我们的临时数组
        return res;
    }
};

时空复杂度分析

时间复杂度: $O(n)O(n)$

理由如下: 我们只是简单的遍历了两次我们的输入进来的数组, 所以我们的时间复杂度是$O(n)O(n)$的

空间复杂度: $O(n)O(n)$

理由如下: 因为我们这个题目给我们的数组是取的引用，所以我们是可以直接在我们原数组上修改的，但是我们开辟了一个新的数组，所以我们的空间复杂度就是$O(n)O(n)$的

解法二

实现思路

我们可以考虑用双指针，一个指针在最左边，一个指针在最右边，然后我们可以先让我们的左边的这个指针一直往后找，如果找到了偶数就停止，我们的右边的指针找到了奇数就停止，然后我们交换这两个位置，这样我们可以保证我们的左指针的左边都是奇数，然后我们的右指针的右边都是偶数

图解代码

代码实现

class Solution {
   public:
    vector<int> reOrderArrayTwo(vector<int>& array) {
        int l = 0, r = array.size() - 1;
        // 左边界的点，和右边的点
        while (l < r) {
            // 我们保证我们始终左边界小于有边界
            while (l < r && array[l] & 1) l++;
            // 找到左边的偶数
            while (l < r && !(array[r] & 1)) r--;
            // 找到右边的奇数
            swap(array[l], array[r]);
            // 交换这两个数字
            // 我们保证我们的l左边都是奇数，r的右边都是偶数
        }
        return array;
    }
};

时空复杂度分析

时间复杂度: $O(n)O(n)$

理由如下: 我们只是简单的遍历了一次数组, 所以我们的时间复杂度是$O(n)O(n)$的

空间复杂度: $O(1)O(1)$

理由如下: 我们只引用了常数级别的空间