2020-10-21 调整顺序使奇数位于偶数前面

题目描述

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

题目分析

整数数组
奇数在偶数前面

参数说明

/**
 * @param {number[]} nums
 * @return {number[]}
 */

题解及实现

1. 逐项反转添加到新数组

新建一个新数组,遍历原数组每一项,如果是奇数就 unshift 到新数组前面,是偶数就 push 到数组后面

var exchange = function (nums) {
  let result = [];
  for (num of nums) {
    num % 2 ? result.unshift(num) : result.push(num);
  }
  return result;
};

时间复杂度:内部实现有关,很慢

资源使用情况
- 执行用时：252 ms, 在所有 JavaScript 提交中击败了 18.16%的用户
- 内存消耗：47.7 MB, 在所有 JavaScript 提交中击败了 5.06%的用户
  问题:新数组空间开销大,前后插入耗费时间

2. 头尾指针法

用两个指针分别指向头尾,从头开始,如果是奇数,头指针后移尾指针不动,如果是偶数,头尾指针指向的数交换,尾指针前移

var exchange = function (nums) {
  if (!nums.length) return [];
  let i = 0;
  let j = nums.length - 1;
  let temp;
  while (i !== j) {
    if (nums[i] % 2) i++;
    else {
      temp = nums[j];
      nums[j--] = nums[i];
      nums[i] = temp;
    }
  }
  return nums;
};

时间复杂度:O(n)

资源使用情况
- 执行用时：84 ms, 在所有 JavaScript 提交中击败了 100.00%的用户
- 内存消耗：45.3 MB, 在所有 JavaScript 提交中击败了 42.55%的用户

3. 快慢指针

用两个指针从头开始,不过他们的速度是不一样的,i 指针负责遍历整个数组,j 指针负责指向下一个奇数应该在的位置,i 指针遍历的过程中,如果是奇数就和 j 指针交换位置,是偶数就继续向前遍历,直到遍历完全

var exchange = function (nums) {
  if (!nums.length) return [];
  if (nums.length === 1) return nums;
  let i = (j = 0);
  let temp;
  while (i < nums.length) {
    if (nums[i] & 1) {
      temp = nums[j];
      nums[j] = nums[i];
      nums[i] = temp;
      j++;
      i++;
    } else i++;
  }
  return nums;
};

时间复杂度:O(n)

资源使用情况
- 执行用时：104 ms, 在所有 JavaScript 提交中击败了98.34%的用户
- 内存消耗：45.2 MB, 在所有 JavaScript 提交中击败了45.74%的用户