C++：调整数组顺序使奇数位于偶数前面【面试】

在C++，如果要调整数组顺序使所有奇数位于偶数前面，这里提供一种简单且常用的方法：双指针技术。这种方法不需要额外的空间，并且时间复杂度为O(n)。

以下是使用双指针技术实现的示例代码：

#include <iostream>
#include <vector>
#include <algorithm> // 用于std::swap
 
void rearrangeArray(std::vector<int>& nums) {
    int left = 0; // 奇数的起始指针
    int right = nums.size() - 1; // 偶数的起始指针
 
    while (left < right) {
        // 左指针向右移动，寻找第一个偶数
        while (left < right && nums[left] % 2 != 0) {
            ++left;
        }
 
        // 右指针向左移动，寻找第一个奇数
        while (left < right && nums[right] % 2 == 0) {
            --right;
        }
 
        // 如果左右指针没有交错，交换两个数
        if (left < right) {
            std::swap(nums[left], nums[right]);
            ++left;
            --right;
        }
    }
}
 
int main() {
    std::vector<int> nums = {1, 4, 3, 6, 9, 2, 7, 8};
    rearrangeArray(nums);
 
    std::cout << "Array after rearrangement: ";
    for (int num : nums) {
        std::cout << num << " ";
    }
    return 0;
}

这段代码中，我们使用了两个指针left和right。初始时，left指向数组的开始，right指向数组的末尾。然后我们分别从左右两边向中间扫描：

• left从左到右找到第一个偶数。
• right从右到左找到第一个奇数。

找到之后，交换这两个数。然后继续这个过程，直到left和right相遇或交错。

这种方法保证了所有的奇数在数组的前半部分，偶数在后半部分，满足了题目要求。

面试回答示例：
"要解决这个问题，我们可以使用双指针技术。首先，我们初始化两个指针，一个指向数组的开始，另一个指向数组的末尾。然后，我们分别从数组的两端向中间扫描，左边的指针寻找偶数，右边的指针寻找奇数。一旦找到，我们就交换这两个数的位置。我们重复这个过程，直到两个指针交错或相遇。这种方法不需要额外的存储空间，并且时间复杂度为O(n)，是一种高效且常用的解决方案。"