905. 按奇偶排序数组

题目描述

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

示例 1：

输入：nums = [3,1,2,4]
输出：[2,4,3,1]
解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。

示例 2：

输入：nums = [0]
输出：[0]

提示：

• 1 <= nums.length <= 5000
• 0 <= nums[i] <= 5000

解题方法

方法一：双指针

• 思路：设置两个指针，遇到偶数就交换两指针指向元素（移动到数组前面）
• 复杂度分析：
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

var sortArrayByParity = function(nums) {
  let i = 0
  let j = 0
  while (j < nums.length) {
    if (nums[j] % 2 === 0) {
      [nums[i], nums[j]] = [nums[j], nums[i]]
      i += 1
    }
    j += 1
  }
  return nums
};

方法二：位运算+排序

• 思路：按奇偶对数组进行排序
  • 比较两个元素进行按位与运算，这会返回他们的最低位(最右边的位)
  • 偶数最低位为 0， 奇数最低位为 1
    • 如果 a 是偶数，b 是奇数，那么(a & 1) - (b & 1) => 0 - 1 是 -1, 会将 a 排在 b 前
    • 如果 a 是奇数，b 是偶数，那么(a & 1) - (b & 1) => 1 - 0 是 -1, 会将 b 排在 a 前
• 复杂度分析：
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(logn), 排序栈

var sortArrayByParity = function(A) {
  return A.sort((a, b) => (a & 1) - (b & 1))
}