922.按奇偶排序数组II

链接：922.按奇偶排序数组II
难度：Easy
标签：数组、双指针、排序
简介：给定一个非负整数数组  A， A 中一半整数是奇数，一半整数是偶数。对数组进行排序，以便当  A[i] 为奇数时，i  也是奇数；当  A[i]  为偶数时， i 也是偶数。

题解 1 - typescript

• 编辑时间：2020-11-12
• 执行用时：120ms
• 内存消耗：44.1MB
• 编程语言：typescript
• 解法介绍：检测当前位置是否符合，不符合查找替换。

function sortArrayByParityII(A: number[]): number[] {
  const len = A.length;
  for (let i = 0; i < len; i++) {
    if (i & 1) {
      if ((A[i] & 1) === 0) {
        let j = i + 1;
        while (j < len) {
          if (A[j] & 1) break;
          j++;
        }
        swap(i, j);
      }
    } else {
      if (A[i] & 1) {
        let j = i + 1;
        while (j < len) {
          if ((A[j] & 1) === 0) break;
          j++;
        }
        swap(i, j);
      }
    }
  }
  function swap(i1: number, i2: number) {
    const t = A[i1];
    A[i1] = A[i2];
    A[i2] = t;
  }
  return A;
}

题解 2 - typescript

• 编辑时间：2020-11-12
• 执行用时：364ms
• 内存消耗：47.1MB
• 编程语言：typescript
• 解法介绍：遍历查找符合的元素。

function sortArrayByParityII(A: number[]): number[] {
  const ans: number[] = [];
  while (A.length !== 0) {
    if (A.length === 1) {
      ans.push(A.pop()!);
    } else {
      const nowLen = ans.length;
      let i = 0;
      if (nowLen & 1) {
        for (; i < A.length; i++) {
          if (A[i] & 1) break;
        }
      } else {
        for (; i < A.length; i++) {
          if ((A[i] & 1) === 0) break;
        }
      }
      ans.push(A.splice(i, 1)[0]);
    }
  }
  return ans;
}

题解 3 - typescript

• 编辑时间：2020-11-12
• 执行用时：140ms
• 内存消耗：47.2MB
• 编程语言：typescript
• 解法介绍：遍历一次储存奇偶。

function sortArrayByParityII(A: number[]): number[] {
  const cache: Record<number, number[]> = { 1: [], 0: [] };
  const ans: number[] = [];
  const len = A.length;
  A.forEach(num => cache[num & 1].push(num));
  let i = 0;
  while (i !== len) {
    ans.push(cache[i++ & 1].pop()!);
  }
  return ans;
}