題目描述

輸入一個整數(shù)數(shù)組,實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序,使得所有奇數(shù)位于數(shù)組的前半部分,所有偶數(shù)位于數(shù)組的后半部分

題目分析

• 整數(shù)數(shù)組
• 奇數(shù)在偶數(shù)前面

參數(shù)說明

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

題解及實現(xiàn)

1. 逐項反轉(zhuǎn)添加到新數(shù)組

新建一個新數(shù)組,遍歷原數(shù)組每一項,如果是奇數(shù)就 unshift 到新數(shù)組前面,是偶數(shù)就 push 到數(shù)組后面

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

時間復(fù)雜度:內(nèi)部實現(xiàn)有關(guān),很慢

• 資源使用情況
  • 執(zhí)行用時：252 ms, 在所有 JavaScript 提交中擊敗了 18.16%的用戶
  • 內(nèi)存消耗：47.7 MB, 在所有 JavaScript 提交中擊敗了 5.06%的用戶
    問題:新數(shù)組空間開銷大,前后插入耗費時間

2. 頭尾指針法

用兩個指針分別指向頭尾,從頭開始,如果是奇數(shù),頭指針后移尾指針不動,如果是偶數(shù),頭尾指針指向的數(shù)交換,尾指針前移

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;
};

時間復(fù)雜度:O(n)

• 資源使用情況
  • 執(zhí)行用時：84 ms, 在所有 JavaScript 提交中擊敗了 100.00%的用戶
  • 內(nèi)存消耗：45.3 MB, 在所有 JavaScript 提交中擊敗了 42.55%的用戶

3. 快慢指針

用兩個指針從頭開始,不過他們的速度是不一樣的,i 指針負(fù)責(zé)遍歷整個數(shù)組,j 指針負(fù)責(zé)指向下一個奇數(shù)應(yīng)該在的位置,i 指針遍歷的過程中,如果是奇數(shù)就和 j 指針交換位置,是偶數(shù)就繼續(xù)向前遍歷,直到遍歷完全

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;
};

時間復(fù)雜度:O(n)

• 資源使用情況
  • 執(zhí)行用時：104 ms, 在所有 JavaScript 提交中擊敗了98.34%的用戶
  • 內(nèi)存消耗：45.2 MB, 在所有 JavaScript 提交中擊敗了45.74%的用戶