调整数组顺序使奇数位于偶数前面

题目

题目来源：力扣（LeetCode）

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

示例：

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

解法一：首尾双指针

使用首尾指针遍历数组，其中头指针寻找偶数，右指针寻找奇数：

• 定义头指针 left，尾指针 right；
• left 一直往右移，直到它指向的值为偶数；
• right 一直往左移，直到它指向的值为奇数；
• 交换 nums[left] 和 nums[right]
• 直到 left == right ，数组遍历完，也已排好序

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var exchange = function(nums) {
  // 头指针
  let left = 0;
  // 尾指针
  let right = nums.length - 1;
  // let temp;
  // 循环遍历
  while (left <= right) {
    // 头指针寻找偶数，如果是奇数，指针进 1
    if (nums[left] % 2 === 1) {
      left++;
      continue;
    }
    // 尾指针寻找奇数，如果是偶数，指针退 1
    if (nums[right] % 2 === 0) {
      right--;
      continue;
    }
    // 若左指针指向为偶数，右指针指向为奇数，则交换对应的值
    // temp = nums[left];
    // nums[left] = nums[right]
    // nums[right] = temp;
    [nums[left], nums[right]]=[nums[right], nums[left]]
    // 值互换后，同时移动头指针和尾指针
    right--;
    left++;
  }
  return nums
};

解法二：快慢指针

我们也可以使用快慢指针遍历数组，其中快指针向前搜索奇数的位置，慢指针指向下一个奇数应当交换的位置：

• 定义快指针fast，慢指针slow，fast 和 slow 都从数组的头部开始遍历
• fast 向前移动，如果它遇到了奇数，则和 nums[slow] 交换，交换后，快指针和慢指针都往前移动一步
• 如果快指针没有遇到奇数，则继续右移，慢指针不动
• 当快指针指向数组末尾时，遍历结束

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var exchange = function(nums) {
  let fast = 0; // 快指针
  let slow = 0; // 慢指针
  let length = nums.length
  while (fast < length) {
    // 快指针fast 遍历到奇数时就要与slow交换元素
    if (nums[fast] & 1) { // n & 1  结果为 1 则 n 为奇数，结果为 0  则 n 为偶数
      // 交换位置
      [nums[fast], nums[slow]] = [nums[slow], nums[fast]];
      // 交换位置之后慢指针往前移动一位，指向下一个奇数应该存放的位置
      slow++
    }
    // 快指针一直挨个遍历到数组末尾结束
    fast++
  }
  return nums
};