「每日LeetCode」2020年11月12日

本文最后更新于：2023年3月19日 晚上

Lt922. 按奇偶排序数组 II

922. 按奇偶排序数组 II

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
示例：

1
2
3
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

提示：

  1. 2 <= A.length <= 20000
  2. A.length % 2 == 0
  3. 0 <= A[i] <= 1000

思路

额外双数组

把原数组奇数偶数分别提取出来，再按偶数奇数的顺序添加回去。

原地修改

遍历一次数组，判断当前位置的元素是否符合要求。例如判断当前是否下标和数都为偶数，不符合就去之后元素中找一个，数为偶数，但是下标为奇数的数，将两个元素交换。

单数组

使用单结果数组，分别使用奇数下标和偶数下标记录元素应该放置的位置，每次放置以后都令下标加 2。

解答

额外双数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParityII = function (A) {
  const oddArr = A.filter((e) => e % 2 !== 0);
  const evenArr = A.filter((e) => e % 2 === 0);
  const res = [];
  while (oddArr.length) {
    res.push(evenArr.pop());
    res.push(oddArr.pop());
  }
  return res;
};

原地修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParityII = function (A) {
  for (let i = 0; i < A.length; i++) {
    if (i % 2 === 0) {
      if (A[i] % 2 === 0) continue;
      else {
        let j = i + 1;
        while (j < A.length) {
          if (A[j] % 2 === 0) {
            [A[i], A[j]] = [A[j], A[i]];
            break;
          }
          j += 2;
        }
      }
    } else {
      if (A[i] % 2 !== 0) continue;
      else {
        let j = i + 1;
        while (j < A.length) {
          if (A[j] % 2 !== 0) {
            [A[i], A[j]] = [A[j], A[i]];
            break;
          }
          j += 2;
        }
      }
    }
  }
  return A;
};

单数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParityII = function (A) {
  const res = [];
  let eIndex = 0,
    oIndex = 1;
  for (const num of A) {
    if (num % 2 === 0) {
      res[eIndex] = num;
      eIndex += 2;
    } else {
      res[oIndex] = num;
      oIndex += 2;
    }
  }
  return res;
};