932.漂亮数组

漂亮数组

如果长度为 n 的数组 nums 满足下述条件，则认为该数组是一个 漂亮数组：

• nums 是由范围 [1, n] 的整数组成的一个排列。
• 对于每个 0 <= i < j < n，均不存在下标 k 满足 i < k < j 且 nums[k] * 2 == nums[i] + nums[j]。

给你整数 n，返回长度为 n 的任意一个漂亮数组。

示例 1:

输入：n = 4
输出：[2,1,4,3]

示例 2:

输入：n = 5
输出：[3,1,2,5,4]

提示:

• 1 <= n <= 1000

解析

使用分治的思想：如果 A 是漂亮数组，那么 2A-1（奇数）和 2A（偶数）也是漂亮数组。将两个漂亮数组连接起来仍然是漂亮数组。

var beautifulArray = function (n) {
  if (n === 1) return [1];

  const left = beautifulArray(Math.floor((n + 1) / 2));
  const right = beautifulArray(Math.floor(n / 2));

  const result = [];
  for (const x of left) {
    result.push(2 * x - 1);
  }
  for (const x of right) {
    result.push(2 * x);
  }

  return result;
};

时间复杂度 O(n log n)，空间复杂度 O(n log n)。