905. 按奇偶排序数组

905. 按奇偶排序数组

leetcode 链接

解法一：遍历数组

创建空数组 res 用来存放结果，遍历 nums，如果值为偶数则 res.unshift(nums[i])，否则 res.push(nums[i])。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function sortArrayByParity(nums) {
  const res = []
  const computedNum = (num) => {
    if ((1 & num) === 0) {
      res.unshift(num)
    }
    else {
      res.push(num)
    }
  }
  for (const num of nums) {
    computedNum(num)
  }
  return res
}

解法二：双指针遍历数组

与方法一相似，只不过创建两个指针，从头尾向中间遍历，这样可缩短一倍遍历次数。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function sortArrayByParity(nums) {
  const res = []
  let i = 0
  let j = nums.length - 1
  const computedNum = (n) => {
    if ((1 & nums[n]) === 0) {
      res.unshift(nums[n])
    }
    else {
      res.push(nums[n])
    }
  }
  while (i < j) {
    computedNum(i)
    computedNum(j)
    i++
    j--
  }
  if (i === j) {
    computedNum(i)
  }
  return res
}

解法三 原地交换

也是创建两个指针，从头开始遍历，直到找到一个奇数，然后再从尾开始遍历找到一个偶数，把这两个位置的值交换，重复以上步骤直至两个指针相遇。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function sortArrayByParity(nums) {
  let left = 0
  let right = nums.length - 1
  while (left < right) {
    while (left < right && (nums[left] & 1) === 0) {
      left++
    }
    while (left < right && (nums[right] & 1) === 1) {
      right--
    }
    const temp = nums[left]
    nums[left] = nums[right]
    nums[right] = temp
    left++
    right--
  }
  return nums
}

:::tip 上面代码中判断偶数的方法使用的是 & 运算符（按位与），也可以使用 num % 2 === 0 来判断。

// 1 4 7 的二进制表示
0b1 // 1
0b100 // 4
0b111 // 7

偶数的二进制最后一位一定是 0，所以与 1 进行 & 操作结果一定是 0。

偶数最后一位一定是 1，所以与 1 进行 & 操作结果一定是 1。 :::