漂亮数组为什么可以用分治构造？奇偶变换如何保持性质？

简化版

漂亮数组要求不存在 i < k < j 使得 A[k] * 2 = A[i] + A[j]。

可以先构造较小规模的漂亮数组，再把它映射成奇数部分和偶数部分。

如果 B 是漂亮数组，那么 2B-1 和 2B 仍然各自漂亮，奇偶之间也不会形成平均数关系。

详细版

分治构造思路是：

构造大小约为 (n+1)/2 的漂亮数组；
把它映射成奇数：2*x - 1；
构造大小约为 n/2 的漂亮数组；
把它映射成偶数：2*x；
拼接奇数部分和偶数部分。

奇数和偶数之间不会让中间值成为平均数，因为一个奇数加一个偶数是奇数，无法等于 2*A[k] 这个偶数。

递归加缓存可以避免重复构造。

完整版教学

一、漂亮数组的条件是什么意思

条件 A[k] * 2 != A[i] + A[j] 表示中间位置的值不能成为前后两个值的平均数。它限制的是位置顺序和数值关系，不是简单升序或降序。构造题的难点在于不能枚举所有排列，而要找到一种能稳定保留性质的生成方式。

记忆钩子：漂亮数组怕“三点成等差”，分治构造靠奇偶隔离。

二、为什么奇偶映射能保持漂亮

如果 B 是漂亮数组，把每个元素映射成 2*x，任意等式都会整体乘以 2，原来的不等式关系保持不变。映射成 2*x-1 也类似，因为等式两边的线性变换会抵消常数项。所以奇数部分内部漂亮，偶数部分内部也漂亮。

若 2*B[k] != B[i] + B[j]
则 2*(2B[k]) != 2B[i] + 2B[j]

线性变换保留了“不是平均数”的结构。

三、为什么奇偶之间不会冲突

跨奇偶部分时，一个数是奇数，一个数是偶数，它们的和是奇数。而 2*A[k] 一定是偶数。奇数不可能等于偶数，所以跨组不会形成违规等式。这就是先放奇数组、再放偶数组的安全性来源。

两端类型	`A[i]+A[j]` 奇偶性	是否可能等于 `2*A[k]`
奇 + 奇	偶数	需要靠组内漂亮性排除
偶 + 偶	偶数	需要靠组内漂亮性排除
奇 + 偶	奇数	不可能

奇偶性帮我们屏蔽了跨组风险。

四、代码模板

实现如下：

function beautifulArray(n) {
  const memo = new Map()
  function build(size) {
    if (memo.has(size)) return memo.get(size)
    if (size === 1) return [1]
    const ans = []
    for (const x of build(Math.floor((size + 1) / 2))) {
      ans.push(2 * x - 1)
    }
    for (const x of build(Math.floor(size / 2))) {
      ans.push(2 * x)
    }
    memo.set(size, ans)
    return ans
  }
  return build(n)
}

递归规模分别是奇数数量和偶数数量，拼出来正好覆盖 1..n。

五、带数字例子

n = 5 时，可以从小规模构造：

build(3) -> [1,3,2]
奇数映射 -> [1,5,3]
build(2) -> [1,2]
偶数映射 -> [2,4]
合并 -> [1,5,3,2,4]

这个数组包含 1..5，并且不会出现位置中间元素等于两端平均数的情况。

六、常见误区与追问

误区：把漂亮数组理解成数值有序。 漂亮数组关注等差关系，不要求升序。
误区：只证明组内漂亮，忘记跨组。 跨组靠奇偶性排除，是构造正确性的关键。
误区：递归不加缓存。 多次构造相同规模会重复计算，缓存更稳。
追问：为什么先奇后偶可以？ 奇偶组之间不会形成平均数冲突，顺序拼接安全。
追问：这是排序题吗？ 不是，这是构造题，目标是满足性质而不是比较大小。

这些问题重点考构造正确性的证明。

七、加强记忆

漂亮数组记成“漂亮可线性变换，奇偶能隔离冲突”。先递归构造小漂亮数组，再映射成奇数和偶数；组内漂亮性来自原数组，跨组安全性来自奇偶和不可能等于偶数。这个题的核心不是代码，而是为什么构造不会破坏性质。

简化版

详细版