漂亮数组

记住这句话,后面每帧都在套它:奇数全靠左、偶数全靠右,跨中点必安全;两侧内部交给规模减半的子问题递归解决。

从最小规模起步。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 最小可拼;另外答案不唯一,只要满足漂亮条件,任何一个都算对。

面试重点:讲清「线性变换保持漂亮」的代数理由,以及「奇偶隔断让两半解耦」如何引出分治。