LeetCode 932. 漂亮数组

2021-08-08 HGNULB 约 10 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 932. 漂亮数组

题意分析

要求给出 $1$ 到 $n$ 的一个排列 A，使得不存在下标 i < k < j 满足 $A[k] \times 2 = A[i] + A[j]$。满足条件的排列叫「漂亮数组」，题目保证一定存在，返回任意一个即可。

先把条件翻译清楚：$A[k] \times 2 = A[i] + A[j]$ 说明 $A[i], A[k], A[j]$ 构成一个等差三项，且中间那项在数组里的位置也恰好夹在两侧之间。所以漂亮数组的本质是：任何等差三元组，都不能按「小-中-大」的顺序在数组中依次出现（这里的顺序指下标顺序，与数值大小无关）。

「返回任意一个」是极强的信号。它意味着这不是搜索题也不是计数题，而是构造题——目标不是找出所有解或最优解，而是设计一套能直接造出合法解的规则。构造题的通用套路是：找一个能自我复制的结构，用递归或迭代把小规模的解拼成大规模的解。

约束里 $n$ 最大 1000，看起来 $O(n^2)$ 甚至 $O(n^2 \log n)$ 的搜索也能跑，但漂亮数组的判定本身就要 $O(n^2)$，回溯的分支又极多，实际上根本搜不出来。约束小只是为了让构造过程的常数不重要。

边界：$n = 1$ 时答案就是 [1]；$n = 2$ 时 [1,2] 已经合法（只有两个元素，凑不出三项）；$n = 3$ 时 [1,3,2] 合法而 [1,2,3] 不合法（1、2、3 正好是顺序出现的等差三项）。

解法：分治构造（奇数部分 + 偶数部分）

核心思路

暴力做法是回溯：逐位放数，每放一个就检查是否与已放的元素构成非法等差三项。检查本身是 $O(n)$ 到 $O(n^2)$，而合法排列在全部 $n!$ 个排列中占比极小，剪枝再狠也搜不动 $n = 1000$。

瓶颈在于我们在「搜索」一个本可以「构造」的东西。于是换个问题：能不能把一个规模为 $m$ 的漂亮数组，机械地变成规模更大的漂亮数组？

关键观察来自等差条件的奇偶性。$A[i] + A[j] = 2 A[k]$ 的右边一定是偶数，所以 $A[i]$ 与 $A[j]$ 必须同奇偶。反过来说：只要 $A[i]$ 与 $A[j]$ 一奇一偶，这个三元组就自动合法，与中间放什么都无关。

这就给出了拼接策略：把数组分成「前半段全是奇数、后半段全是偶数」。此时任何跨越两段的 $(i, j)$ 对都是一奇一偶，永远不会违规；剩下要担心的只有「两个下标都在奇数段内」和「都在偶数段内」两种情况——也就是说，只要奇数段自身是漂亮的、偶数段自身也是漂亮的，整体就是漂亮的。

接下来是第二个观察：漂亮性对仿射变换免疫。若 $B$ 是漂亮数组，则把每个元素做 $x \mapsto 2x - 1$（映射成奇数）或 $x \mapsto 2x$（映射成偶数），得到的数组仍然漂亮。因为等差条件 $2 A[k] = A[i] + A[j]$ 在两边同乘一个正数、同加一个常数之后依然等价——变换后成立当且仅当变换前成立，而变换前不成立，所以变换后也不成立。

两个观察合起来就是完整的构造：设 $B$ 是 $1 \dots m$ 的漂亮数组，那么
\[A = [\,2b - 1 \mid b \in B\,] \; \Vert \; [\,2b \mid b \in B\,]\]
是 $1 \dots 2m$ 的漂亮数组。前半段是所有奇数、后半段是所有偶数，各自由漂亮数组仿射而来因而漂亮，跨段的对因奇偶不同而免检。

不变量：每轮迭代结束后，res 是「$1$ 到 $n$ 中所有能被当前构造覆盖到的数」的一个漂亮排列。由于我们在生成时用 v <= n 过滤掉超界的值，res 始终只含 $1$ 到 $n$ 之间的数、互不重复，且长度单调增大——每轮至少翻倍直到达到 $n$。

过滤为什么不破坏漂亮性？因为漂亮性是关于「不存在某种三元组」的性质，删掉若干元素只会让候选三元组变少，不可能凭空造出违规组合。这是构造题里非常好用的一条：子序列继承父序列的「不存在型」性质。

从 [1] 出发迭代，长度序列是 $1 \to 2 \to 4 \to 8 \to \dots$，最多 $\lceil \log_2 n \rceil$ 轮就能覆盖到 $n$。

解题步骤

初始化 res = [1]：单元素数组必然漂亮（凑不出三项），它是整个构造的种子。

循环条件 res.size() < n：长度达到 n 就停。因为每轮生成时已过滤超界值，最终长度恰好是 n，不会超过。

每轮新建 tmp，先放奇数部分：对 res 中每个 x 计算 2x - 1，<= n 才加入。奇数必须放在前面——顺序不能颠倒，虽然「偶数在前奇数在后」同样满足奇偶跨段免检，但下一轮的映射 2x-1 与 2x 是按当前顺序作用的，混用两种顺序会让推理失去一致性；固定一种写法最稳妥。

再放偶数部分：对每个 x 计算 2x，<= n 才加入。两个循环必须分开写，不能在同一个循环里交替追加——那样奇偶就交错了，跨段免检的前提直接崩塌。

res = tmp 进入下一轮：新数组是旧数组的两倍规模（去掉超界后可能不足两倍）。

循环结束后转成 int[] 返回：Java 里 List<Integer> 需要手动拆箱写入数组；Go 里 res 本身就是 []int，直接返回。

以 n = 5 走一遍。

初始：res = [1]，长度 1 < 5。

第 1 轮：奇数部分对 x = 1 得 2*1-1 = 1，不超过 5，加入；偶数部分得 2*1 = 2，加入。res = [1, 2]，长度 2 < 5。此时前半段 [1] 全奇、后半段 [2] 全偶。

第 2 轮：奇数部分依次得 2*1-1 = 1、2*2-1 = 3，都加入；偶数部分得 2*1 = 2、2*2 = 4，都加入。res = [1, 3, 2, 4]，长度 4 < 5。检验一下：唯一可能的等差三项是 (1,2,3)，而 2 在数组里的位置（下标 2）不在 1（下标 0）和 3（下标 1）之间，合法。

第 3 轮：奇数部分对 [1,3,2,4] 依次得 1、5、3、7；7 > 5 被过滤，得到 [1, 5, 3]。偶数部分依次得 2、6、4、8；6 和 8 都超界被过滤，得到 [2, 4]。拼起来 res = [1, 5, 3, 2, 4]，长度 5，循环结束。

返回 [1, 5, 3, 2, 4]。逐个验证中间项：A[1] = 5，左边只有 1，右边有 3、2、4，需要 1 + ? = 10 即 9，不在数组里；A[2] = 3，需要左右各取一个凑成 6，左边 {1,5}、右边 {2,4}，组合得到 3、5、7、9，没有 6；A[3] = 2，需要凑成 4，左边 {1,5,3}、右边 {4}，组合得 5、9、7，没有 4。全部通过，确实是漂亮数组。

再看「奇偶分段」为什么必要：如果第 2 轮把结果写成交错的 [1, 2, 3, 4]，那么 1、2、3 就按顺序出现了，2*2 = 1 + 3 直接违规。分段的意义正是让所有跨段配对因奇偶不同而免检。

代码实现

class Solution {
    public int[] beautifulArray(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(1);

        while (res.size() < n) {
            List<Integer> tmp = new ArrayList<>(n);
            for (int x : res) {
                int v = 2 * x - 1;
                if (v <= n) {
                    tmp.add(v);
                }
            }
            for (int x : res) {
                int v = 2 * x;
                if (v <= n) {
                    tmp.add(v);
                }
            }
            res = tmp;
        }

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = res.get(i);
        }
        return answer;
    }
}

func beautifulArray(n int) []int {
    res := []int{1}
    for len(res) < n {
        tmp := make([]int, 0, n)
        for _, x := range res {
            v := 2*x - 1
            if v <= n {
                tmp = append(tmp, v)
            }
        }
        for _, x := range res {
            v := 2 * x
            if v <= n {
                tmp = append(tmp, v)
            }
        }
        res = tmp
    }
    return res
}

复杂度分析

时间复杂度：$O(n \log n)$。共 $\lceil \log_2 n \rceil$ 轮，每轮遍历当前 res（长度不超过 $n$）两次做映射与过滤，单轮 $O(n)$。若不考虑被过滤掉的元素，实际总工作量接近 $O(n)$。

空间复杂度：$O(n)$。同一时刻只存在 res 与 tmp 两个长度不超过 $n$ 的列表，轮末旧数组即可回收；最终结果数组本身也是 $O(n)$。

关键点总结

「返回任意一个满足条件的解」是构造题的标志。此时应当放弃搜索，转而寻找能自我复制的结构——把规模 $m$ 的解机械地放大成规模 $2m$ 的解。

等差条件 $2A[k] = A[i] + A[j]$ 要求两端同奇偶，因此「奇数全排前面、偶数全排后面」就让所有跨段配对自动免检，问题被干净地拆成两个独立子问题。

漂亮性对仿射变换 $x \mapsto ax + b$（$a > 0$）免疫，这是把子问题的解搬回原问题的桥梁；能说清「为什么变换保持性质」比记住 2x-1 和 2x 更重要。

「不存在型」性质会被子序列继承，所以生成时直接用 v <= n 过滤超界元素不会破坏漂亮性——这条性质让构造不必凑成 2 的幂次长度。

奇数段与偶数段必须整段分开、不能交错。交错会让同段内的元素跨越到对方位置，跨段免检的前提立刻失效。

面试视角：这题几乎不可能现场推出来，考的是能否在被提示「考虑奇偶性」后迅速补完证明。主动说出「两端同奇偶才可能违规」和「仿射变换保持性质」两句，就是完整答案。

易错点总结

奇数段与偶数段交错生成：n = 4 会得到 [1,2,3,4]，其中 1、2、3 按序出现且 2*2 = 1+3，直接违规。必须先整段放奇数、再整段放偶数。

映射写成 2x + 1 而不是 2x - 1：n = 3 时由 [1] 得到 [3, 2]，数字 1 永远不会出现，结果不是 $1 \dots n$ 的排列。

生成时不过滤 v <= n：n = 5 会产出 7、6、8 等超界值，返回的数组既超界又超长，判题直接判错。

循环条件写成 res.size() <= n：长度恰好等于 n 时还会再跑一轮，虽然过滤后长度不变，但会陷入死循环（每轮结果完全相同）。

在同一个循环里同时追加 2x-1 和 2x：等价于交错，后果同第一条。两个 for 必须分开。

初始种子写成 [] 或 [0]：空列表会让循环永远生成不出元素而死循环；[0] 会映射出 -1 和 0，超出 $1 \dots n$ 的值域。

用回溯搜索并指望剪枝救场：$n = 1000$ 时合法排列在 $n!$ 中占比极低，判定又要 $O(n)$，无论怎么剪都跑不完。

误以为条件是「不存在等差三项」：条件还要求中间项的下标夹在两端之间。[1,3,2] 中 1、2、3 是等差三项，但 2 在最后，完全合法；按「不存在等差三项」理解会认为 $n = 3$ 无解。

误以为条件与数值大小顺序有关：$i < k < j$ 说的是下标顺序，$A[i]$ 未必小于 $A[j]$。把条件读成「递增三项」会漏掉一半的违规情形。

Java 里忘记把 List<Integer> 拆箱成 int[]：返回类型不匹配直接编译失败；用流式 mapToInt 或手写循环都可以，但不能直接返回列表。

试图返回字典序最小的漂亮数组：题目只要求任意一个，追加最小性约束会让构造失效且没有必要。

相似题目

题目	难度	考察点
89. 格雷编码	中等	同为「由 $m$ 位解镜像拼出 $m+1$ 位解」的构造题，答案同样不唯一
241. 为运算表达式设计优先级	中等	按运算符切分左右子问题再合并所有组合，是分治「拆-解-并」的标准形态
95. 不同的二叉搜索树 II	中等	枚举根节点划分区间递归建树，同样把子问题的解直接搬进父问题
面试题 08.06. 汉诺塔问题	简单	递归构造操作序列而非数组，考的是「相信子问题已解决」的思维方式
面试题 08.05. 递归乘法	中等	借助倍增与奇偶拆分把规模减半，与本题的 $2x$ / $2x-1$ 思路同源