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])两边同除以kk ≠ 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的漂亮数组已经被构造出来则对长度为N - N/2的漂亮数组中的每个数a施加映射2a - 1得到全为奇数且覆盖[1, N]中全部奇数的漂亮数组对长度为N / 2的漂亮数组中的每个数b施加映射2b得到全为偶数且覆盖[1, N]中全部偶数的漂亮数组由性质 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考