【算法-剑指 Offer】21. 调整数组顺序使奇数位于偶数前面（双指针；快速排序）

2021-08-15 14:05:40

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode）

文章起笔：2021年11月14日10:50:21

问题描述及示例

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

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

提示:
0 <= nums.length <= 50000
0 <= nums[i] <= 10000

我的题解

我的题解1（单纯遍历）

最直接的方法就是先创建一个 result 数组来接收调整顺序后的数组。然后逐个遍历 nums 数组，如果当前遍历元素是奇数，就利用数组对象的 unshift() 方法将其存入 result 头部；如果当前遍历元素是偶数，就利用数组对象的 push() 方法将其存入 result 尾部。最后返回 result 即可。这种方法比较简单直接，就不再逐行注释了。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var exchange = function(nums) {
  let result = [];
  for(let i = 0; i < nums.length; i++) {
    if(nums[i] % 2) {
      result.unshift(nums[i]);
      continue;
    }
    result.push(nums[i]);
  }
  return result;
};


提交记录
执行结果：通过
17 / 17 个通过测试用例
执行用时：216 ms, 在所有 JavaScript 提交中击败了12.89%的用户
内存消耗：47.1 MB, 在所有 JavaScript 提交中击败了18.07%的用户
时间：2021/11/14 11:01

可以看到，上面这种方法虽然简单直接，但是空间表现和时间表现都不怎么好。

我的题解2（双指针；一趟快速排序）

于是我就想起了快速排序里面一趟排序的过程。在快速排序的一趟排序过程中，我们以某个元素作为基准，把所有小于该元素的数组元素都放在该元素的左边，把所有大于等于该元素的数组元素都放在该元素的右边，这里我们交换元素的判断条件是当前元素和基准元素的大小比较结果。

而本题中，我们交换元素的判断条件是当前元素的奇偶性。

首先创建 low 和 high 两个指针分别指向 nums 的头和尾。并同时将 nums[0] 作为基准，将其值暂存在 base 变量中（其实这里取哪个元素作为基准都可以，为了方便表述，我选择了 nums[0]）。此时就可以将 nums[0] 看做是空元素了。
然后让 high 指针往前移动，直到发现 high 指向的元素为奇数，此时则将 nums[high] 调换至 low 指针指向的地方。此时就可以将 nums[high] 看做是空元素了。
然后让 low 指针往后移动，直到发现 low 指向的元素为偶数，此时则将 nums[low] 调换至 high 指针指向的地方。此时就可以将 nums[low] 看做是空元素了。
重复上面的调换过程，直到 low 指针和 high 指针都指向同一个元素。此时，再将基准元素放到 low 指针指向的地方，那么就可以保证 low 指针指向的地方左侧的元素都是奇数，而其右侧的元素都是偶数。此时就算是完成了一趟快速排序过程了。

这里不用担心基准元素的奇偶性，因为作为奇偶数的分界点，它本身的奇偶性并不会影响最后的结果的正确性。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var exchange = function(nums) {
  // 如果nums为空，则需要特别处理，否则的话，最后会返回 [undefined]
  if(!nums.length) {
    return [];
  }
  // low指针初始指向nums头部
  let low = 0;
  // high指针初始指向nums尾部
  let high = nums.length - 1;
  // base用于暂存基准元素（当然在本题中，可能叫做分界点元素会比较好）
  // 此时就可以把 nums[low] 看做是空元素了
  let base = nums[0];
  // 只要low和high没有指向同一个元素，那么就要继续交换过程
  while(low < high) {
    // high指针往前移动，直到遇到奇数，注意这里要时刻保持 low < high，下面的判断也是同理
    while(low < high && !(nums[high] % 2)) {
      high--;
    }
    // 调换nums[low] 和 nums[high]，此时就可以把 nums[high] 看做是空元素了
    if(low < high) {
      nums[low] = nums[high];
      low++;
    }
    // low指针往前移动，直到遇到奇数
    while(low < high && nums[low] % 2) {
      low++;
    }
    // 调换nums[low] 和 nums[high]，此时就可以把 nums[low] 看做是空元素了
    if(low < high) {
      nums[high] = nums[low];
      high--;
    }
  }
  // 最后low和high指针指向同一个元素，该元素即为交界点，则将基准元素放入该交界点
  nums[low] = base;
  return nums;
};


提交记录
执行结果：通过
17 / 17 个通过测试用例
执行用时：92 ms, 在所有 JavaScript 提交中击败了86.18%的用户
内存消耗：45.2 MB, 在所有 JavaScript 提交中击败了73.95%的用户
时间：2021/11/14 10:53

官方题解

更新：2021年7月29日18:43:21

因为我考虑到著作权归属问题，所以【官方题解】部分我不再粘贴具体的代码了，可到下方的链接中查看。

【更新结束】

更新：2021年11月14日11:00:27

参考：剑指 Offer 21. 调整数组顺序使奇数位于偶数前面（双指针，清晰图解） - 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode）

注意，以上为【官方精选题解】。

【更新结束】

有关参考

《数据结构——用C语言描述（第二版）》P328~P331 耿国华、张德同、周明全等编著——高等教育出版社

码农公寓