企业官网建设流程全解析

LeetCode 题解 932：漂亮数组（Beautiful Array）的分治构造法解析

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本文深入解析 LeetCode 932「漂亮数组（Beautiful Array）」这道经典分治构造题，围绕"奇数 + 偶数 = 奇数"这一奇偶性质，推导出漂亮数组在线性变换下保持封闭、以及不同奇偶性漂亮数组可直接拼接的两条核心性质，并据此给出递归分治构造的完整实现与复杂度证明。读完本文，你将掌握一类"按奇偶性二分 + 线性映射"的数组构造题通法，并能举一反三地应用分治与记忆化缓存（Memoization）的组合套路。

题目描述

对于某些固定的N，如果数组A是整数1, 2, ..., N组成的排列，使得：

对于每个i < j，都不存在k满足i < k < j使得A[k] * 2 = A[i] + A[j]。

那么数组A是漂亮数组（Beautiful Array）。

给定N，返回任意漂亮数组A（保证存在一个）。

示例 1：

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

示例 2：

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

提示：

• 1 <= N <= 1000

本题目录收录于 problems/932.beautiful-array.md，并在仓库 README.md、SUMMARY.md 与 introduction.md 的题解目录中登记为 0932。

前置知识与考点定位

原题解给出的前置知识为分治。结合仓库中 基础算法 的梳理，分治思想在 LeetCode 中贯穿排序（快排、归并）、查找与各类构造题；而本题的独特之处在于，它不仅仅"分而治之"，还要求在合并阶段利用数学性质保证最终排列满足约束，属于典型的构造性分治。

此外，实现中用到了记忆化递归（@lru_cache），这部分思想在仓库的 动态规划专题 中有系统阐述，读者可将本题视为"递归 + 缓存"在构造场景下的应用范例。

核心思路：抓住奇偶性

问题的等价理解

约束条件A[k] * 2 = A[i] + A[j]要求：在任意三个下标 i < k < j 中，中间元素的值不能是两端元素值的平均数。换言之，漂亮数组不允许出现"中间元素恰好是两端中点"的三元组。

由数字的奇偶特性，可知：

奇数 + 偶数 = 奇数

因此如果A[i]和A[j]一个是奇数、另一个是偶数，那么A[i] + A[j]必为奇数；而A[k] * 2恒为偶数。偶数不可能等于奇数，所以这样的三元组自动被排除。只要让任意一对"跨中间下标"的元素一奇一偶，约束即天然满足。

两条关键性质

原题解给出了本题的两条突破口性质，这里展开说明：

性质 1（线性映射保持性）：如果数组A是漂亮数组，那么将A中的每一个数x进行kx + b的映射，其仍然为漂亮数组。其中k为不等于 0 的整数，b为整数。

证明要点：若映射后出现(k*A[k]+b) * 2 = (k*A[i]+b) + (k*A[j]+b)，化简得2k*A[k] = k*(A[i]+A[j])，两边同除以k（k ≠ 0）得到2*A[k] = A[i]+A[j]，与A是漂亮数组矛盾。因此映射保持漂亮性质。特别地，2x - 1把数变为奇数，2x把数变为偶数。

性质 2（异奇偶拼接保持性）：如果数组A和B分别是不同奇偶性的漂亮数组（即一个全为奇数、一个全为偶数），那么将A和B拼接起来仍为漂亮数组。

证明要点：拼接后，跨越两个子数组边界的三元组中，两个端点必然分别位于奇数段和偶数段（或反之），其一奇一偶，由"奇数 + 偶数 = 奇数 ≠ 偶数"可知不会构成非法三元组；而各段内部本身已是漂亮数组，约束自然成立。

分治构造的推导

我们要求长度为N的漂亮数组。区间[1, N]内，偶数的个数为N / 2（地板除），奇数的个数为N - N / 2。

假设长度为N / 2和N - N / 2的漂亮数组已经被构造出来，则：

1. 对长度为N - N/2的漂亮数组中的每个数a施加映射2a - 1，得到全为奇数且覆盖[1, N]中全部奇数的漂亮数组；
2. 对长度为N / 2的漂亮数组中的每个数b施加映射2b，得到全为偶数且覆盖[1, N]中全部偶数的漂亮数组；
3. 由性质 2，将奇数段与偶数段拼接，即得到长度为N的漂亮数组。

而"长度为N / 2与N - N / 2的漂亮数组"我们尚未算出，这正好构成递归：用同样方法继续分解，问题规模不断缩小而本质不变。递归的终点是N == 1，此时可直接返回[1]。

手动推演：N = 4 与 N = 5

以N = 4为例：

• 奇数个数为4 - 2 = 2，偶数个数为2；
• 递归求dp(2)：奇数段来自dp(1) = [1]映射为[1]，偶数段来自dp(1)映射为[2]，拼接得[1, 2]；
• 回到N = 4：奇数段为dp(2)中每个元素2a-1→[1, 3]，偶数段为dp(2)中每个元素2b→[2, 4]，拼接得[1, 3, 2, 4]。

该结果与题目示例输出[2,1,4,3]不同，但同样合法——题目只要求返回任意一个漂亮数组，构造顺序不同会得到不同的合法排列。

以N = 5为例：

• 奇数个数为5 - 2 = 3，偶数个数为2；
• 递归求dp(3)：奇数段为dp(2)映射2a-1→[1, 3]，偶数段为dp(1)映射2b→[2]，拼接得[1, 3, 2]；dp(2) = [1, 2]；
• 回到N = 5：奇数段为dp(3)中每个元素2a-1→[1, 5, 3]，偶数段为dp(2)中每个元素2b→[2, 4]，拼接得[1, 5, 3, 2, 4]。

这也是一个合法答案，与题示例输出[3,1,2,5,4]同为有效构造。

代码实现

原题解提供 Python3 实现，采用自顶向下递归 +lru_cache记忆化：

class Solution: def beautifulArray(self, N: int) -> List[int]: @lru_cache(None) def dp(n): if n == 1: return [1] ans = [] # [1,n] 中奇数比偶数多1或一样 for a in dp(n - n // 2): ans += [a * 2 - 1] for b in dp(n // 2): ans += [b * 2] return ans return dp(N)

实现要点解读：

• dp(n - n // 2)对应奇数个数N - N/2，映射a * 2 - 1将其转化为覆盖[1, n]中全部奇数的奇数段；
• dp(n // 2)对应偶数个数N / 2，映射b * 2将其转化为覆盖[1, n]中全部偶数的偶数段；
• 奇数段在前、偶数段在后拼接，恰好对应[1, n]的奇偶分布（奇数比偶数多 1 或两者相等）；
• @lru_cache(None)对dp(n)的结果进行缓存：递归树中同一规模的子问题只计算一次，避免指数级重复计算，这也是本题能在N <= 1000约束下高效运行的关键。

上述递归逻辑也可以改写成自底向上的递推版本，从[1]出发逐层放大：每一轮把上一轮结果分别映射为奇数段与偶数段后拼接，迭代O(log N)轮即可得到长度为N的答案。两种写法的构造原理完全一致，读者可以自行验证结果的一致性。

复杂度分析

令n为数组长度。

• 时间复杂度：O(n log n)。每一层递归需要遍历当前规模的数组进行线性映射，递归深度为O(log n)，每层总工作量合计为O(n)，故整体为O(n log n)；
• 空间复杂度：O(n + log n)。lru_cache缓存了所有规模子问题的结果，总数据量为O(n)；递归调用栈深度为O(log n)。

相关专题与仓库资源

本题是"分治 + 奇偶性 + 线性映射"三类技巧的综合运用，仓库中与其可互相印证的资源包括：

• 动态规划专题：系统讲解递归与记忆化（Memoization）的适用场景，@lru_cache正是该思想的语言级实现；
• 搜索专题：该文档也提及可用类似分治的方式逐步确定答案，与本题的"逐层构造"思路相通；
• 基础算法：梳理了分治在快排、归并等算法中的应用，可作为理解本题合并步骤的背景；
• 91.decode-ways.md：同仓库中另一道依赖"递归 + 记忆化"的题目，可对比感受记忆化在计数类与构造类问题中的统一用法。

小结

漂亮数组的构造核心只有三句话：让任意跨中点的两端一奇一偶，靠2x - 1与2x两个线性映射分离奇偶，再靠分治递归缩小规模、自底向上拼接。理解性质 1 的线性映射保持性与性质 2 的异奇偶拼接性之后，这道题就转化为一个干净的递归构造过程；配合记忆化缓存，即可在O(n log n)时间内对N <= 1000的任何输入给出合法答案。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode