905. 按奇偶排序数组

905. 按奇偶排序数组

leetcode 链接

解法一：遍历数组

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

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArrayByParity = function (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[]}
 */
var sortArrayByParity = function (nums) {
  const res = [];
  let i = 0,
    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[]}
 */
var sortArrayByParity = function (nums) {
  let left = 0,
    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。 :::