题目描述
思路解析
一句话答案：LeetCode 932 漂亮数组：任意 i＜k＜j 都没有 2·A[k]=A[i]+A[j]。不枚举排列，改用分治——奇数全堆左、偶数全堆右，跨中点和为奇凑不出偶数的 2 倍中点，两侧再各自递归，O(n log n)。
1 到 n 的排列，要躲开什么样的三元组
给定 n，要输出 1 到 n 的一个排列，即这 n 个数各用一次重排一遍。「漂亮」指：任取位置 i＜k＜j，中间的 nums[k] 不能是两端的平均，即不存在 2×nums[k]=nums[i]+nums[j]。题面 n=5 的答案之一是 [1, 5, 3, 2, 4]，返回任一即可。
为什么不能把排列一个个列出来验
n 的排列有 n! 个——n! 就是 1 一路乘到 n，n=5 才 120 种、n=10 已三百多万，逐个生成再用三重循环 O(n³) 验违规三元组，稍大就跑不完。得换条不靠枚举、直接拼答案的路。
奇数堆左、偶数堆右，凭什么跨中点就安全
先盯住要躲开的等式 2×nums[k]=nums[i]+nums[j]。左边 2 乘整数必是偶数，右边 nums[i]+nums[j] 也得是偶数，而两数之和为偶，当且仅当它俩同奇偶。反过来，两端一奇一偶、和为奇，就碰不上左边的偶数。
顺着这点摆出隔断：奇数全放左半、偶数全放右半。凡跨越分界的三元组，两端一个取自奇数区、一个取自偶数区，和为奇，2 倍中点是偶，绝不相等。横跨中线的三元组全排除，只剩两端同在一侧要管。
同一侧内部交给谁，映射为什么不弄丢漂亮
同侧内部的三元组，丢给规模减半的同类子问题各自去解——把大问题切成互不打架的小块，这就是分治。左半装 1 到 n 的奇数，共 ceil(n/2) 个，除不尽向上进一；右半偶数 floor(n/2) 个，除不尽向下砍。递归求 ceil(n/2) 长的漂亮排列，每个数 x→2x-1 映射成奇数；右半同理 x→2x 映射成偶数。地基 n=1，单独的 1 已漂亮。
映射为什么不弄丢漂亮？2x-1 和 2x 都是 x→ax+b 这个样子，把整组数按同比例放大、再整体挪一段；代入判定等式，常数项与公因子成对约掉后回原式，素材漂亮映射完照样漂亮。
n=5 顺着搭一遍，答案是怎么拼出来的
从地基往上搭。n=1 是 [1]；n=2 拼成 [1, 2]。n=3：奇数 2 个偶数 1 个，奇侧拿 [1, 2] 映射 2x-1 得 [1, 3]、偶侧拿 [1] 得 [2]，拼成 [1, 3, 2]。
到 n=5：奇数 3 个、偶数 2 个。奇侧素材是 [1, 3, 2]，逐个 2x-1：1 变 1、3 变 5、2 变 3，得 [1, 5, 3]。偶侧素材 [1, 2]，逐个 2x 得 [2, 4]。奇左偶右拼起来，就是 [1, 5, 3, 2, 4]。
映射配错个数，就拼不出 1 到 n 的排列
复杂度上，每层把两半映射再拼接、工作量随当前长度走，合起来 O(n)；长度每次减半、约 log n 层，总时间 O(n log n)（无备忘录，把每层 O(n) 累起来）。空间是输出和临时数组，峰值 O(n)、递归栈 O(log n)。
两处配错会拼坏答案。映射别对调：2x-1 生奇数、2x 生偶数，反了则跨中点不再安全。规模别分反：奇侧配 ceil(n/2)、偶侧配 floor(n/2)，恰是 1 到 n 里奇、偶数的个数，配错会漏数或造重复值、拼不成排列。构造已保证漂亮，不必再写三重循环验一遍。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句话,后面每帧都在套它:奇数全靠左、偶数全靠右,跨中点必安全;两侧内部交给规模减半的子问题递归解决。
从最小规模起步。n=1 时只有一个数 1,孤零零一个数当然漂亮,它是整套递归的地基。后面所有更大的漂亮数组,都从它一层层搭上来。
现在搭 n=2。奇数个数是 1 个、偶数个数是 1 个,所以奇侧和偶侧都拿地基 f(1)=[1] 当素材。下面把它分别映射成「全奇」和「全偶」。
奇侧用映射 2x-1。把素材里的 1 代进去,2 乘 1 减 1 还是 1,这是一个奇数。奇侧得到 [1]。
偶侧用映射 2x。同样把 1 代进去,2 乘 1 等于 2,这是一个偶数。偶侧得到 [2]。
奇侧放左、偶侧放右,拼成 [1, 2]。这就是 f(2),存进右边的备忘录,后面更大的规模会反复取用它。
验一下:只有 1 和 2 这一对,中间根本没有别的数能当中点,自然没法违规。f(2) 漂亮,稳。
搭 n=3。1 到 3 里奇数有 2 个、偶数有 1 个,所以奇侧拿 f(2)=[1, 2],偶侧拿 f(1)=[1]。素材都已经是漂亮的,放心映射。
奇侧逐个映射。第一个素材是 1,代进 2x-1 得 1。奇侧第一格填好,先是 [1, 空]。
第二个素材是 2,代进 2x-1 得 3,又是个奇数。奇侧凑齐成 [1, 3],两个都是奇数,符合预期。
偶侧素材是 f(1)=[1],映射 2x 得 2。偶侧只有一格,就是 [2]。
奇侧 [1, 3] 放左、偶侧 [2] 放右,拼成 [1, 3, 2]。这就是 f(3),同样存进备忘录。
检验唯一的三元组:两端是 1 和 2,中点是 3。2 乘中点 3 等于 6,两端之和才 3,根本不等。f(3) 漂亮。
终于到目标 n=5。1 到 5 里奇数 3 个、偶数 2 个,奇侧拿 f(3)=[1, 3, 2],偶侧拿 f(2)=[1, 2]。两份素材备忘录里都现成,直接映射。
奇侧映射开始。素材第一个 1,代进 2x-1 得 1。奇侧先填 [1, 空, 空]。
素材第二个 3,代进 2x-1 得 5。奇侧填到 [1, 5, 空]。注意得到的都是奇数,这正是「奇侧」名字的由来。
素材第三个 2,代进 2x-1 得 3。奇侧凑齐 [1, 5, 3],三个全是奇数。左半部分搞定。
换到偶侧,素材是 f(2)=[1, 2]。第一个 1 代进 2x 得 2。偶侧先填 [2, 空]。
第二个 2 代进 2x 得 4。偶侧凑齐 [2, 4],两个都是偶数。右半部分也搞定。
奇侧 [1, 5, 3] 放左、偶侧 [2, 4] 放右,拼成 [1, 5, 3, 2, 4]。左边三个全奇、右边两个全偶,这就是 n=5 的漂亮数组。
看为什么对。只要一对位置跨过了「奇偶分界线」,左端是奇数、右端是偶数,两端之和是奇数;而 2 乘任何中点都是偶数,一奇一偶绝不可能相等。所有跨界三元组天然安全。
那同一侧内部呢?左边这三个奇数,本质就是 f(3) 做了一次 2x-1 的整体变换。这种线性变换不会破坏「漂亮」性质,而 f(3) 我们已经验过是漂亮的,所以左侧内部也安全。偶侧同理。
两块拼起来:跨界的三元组安全,各侧内部也安全,整个数组就是漂亮的。n=5 的答案锁定为 [1, 5, 3, 2, 4]。题目允许任一漂亮数组,这一个就行。
边界要点:n=1 是递归终点,n=2 最小可拼;另外答案不唯一,只要满足漂亮条件,任何一个都算对。
面试重点:讲清「线性变换保持漂亮」的代数理由,以及「奇偶隔断让两半解耦」如何引出分治。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def beautifulArray(self, n: int) -> List[int]: if n == 1: return [1] left = self.beautifulArray((n + 1) >> 1) right = self.beautifulArray(n >> 1) left = [x * 2 - 1 for x in left] right = [x * 2 for x in right] return left + right复杂度
- 时间：O(n log n)，无备忘录;每层合并共 O(n),递归约 log n 层
- 空间：O(n)，输出+临时数组峰值 O(n),递归栈 O(log n)
易错点
面试追问把动画讲成自己的话
追问为什么把漂亮数组每个元素做 2x-1 或 2x 这种线性变换后,它依然漂亮?
追问这道题怎么想到用分治?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
查询后的偶数和
LeetCode 985 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题