leetcode 链接：剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

  1. 输入：nums = [1,2,3,4]
  2. 输出：[1,3,2,4] 
  3. 注：[3,1,2,4] 也是正确的答案之一。

解答 & 代码

解法一：额外数组

建立额外的数组 oddNums 和 evenNums，分别用于存储奇数和偶数。
遍历数组 nums，如果当前元素是奇数，则存入 oddNums，否则存入 evenNums
遍历完后，依次将 oddNums 和 evenNums 写入数组 nums

时间复杂度 O(N)，空间复杂度 O(N)

解法二：快排 partition 的思想

使用快排分割函数（partition）的思想，只不过只需要进行一次，因此时间复杂度 O(N)，空间复杂度 O(1)

  • 初始化：
    • 将数组第一个元素 nums[0] 作为分割基准，记为 tmp
    • left = 0, right = len - 1。left 是第一个空位置
  • 使用 left、right 双指针从两边往里遍历数组，直到 left == right
    • right 先往左遍历，找到第一个奇数，放到左边的空位，得到新的空位即 right
    • left 往右遍历，找到第一个偶数，放到右边的空位，得到新的空位即 left

  • 遍历完后，将当前的空位 nums[left] 填上 tmp。因为遍历完后 left 左边都是奇数，右边都是偶数，left 是奇偶交界的位置，填入的 tmp 是奇是偶无所谓

    class Solution {
public:
  vector<int> exchange(vector<int>& nums) {
      int len = nums.size();
      if(len <= 1)
          return nums;

      int tmp = nums[0];
      int left = 0, right = len - 1;
      while(left < right)
      {
          while(left < right && nums[right] % 2 == 0)
              --right;
          nums[left] = nums[right];
          while(left < right && nums[left] % 2 == 1)
              ++left;
          nums[right] = nums[left];
      }
      nums[left] = tmp;
      return nums;
  }
};

    执行结果： ``` 执行结果：通过

执行用时：20 ms, 在所有 C++ 提交中击败了 82.69% 的用户 内存消耗：17.8 MB, 在所有 C++ 提交中击败了 12.20% 的用户 ```