What is the core trick in Beautiful Array?

The trick is to build a smaller beautiful array first, then map it to odd values with 2x-1 and even values with 2x. Concatenating those two groups preserves the no-average rule because parity blocks cross-group midpoint conflicts.

Why does the odd-even construction work for the Array plus Math pattern?

Within the odd group and within the even group, the original relative structure is preserved from the smaller beautiful array. Across groups, one endpoint is odd and the other is even, so their average cannot land as a valid middle element in the required way for this construction.

Do I need to verify every i, k, j triple after building the array?

No. The point of the construction is that the proof gives you the guarantee. Once you correctly generate the array through the recursive odd and even mapping, explicit triple checking is unnecessary.

Why is brute force a bad fit for LeetCode 932?

Brute force treats Beautiful Array like a search problem over permutations, which grows far too fast and still needs expensive validation. The intended solution is constructive divide and conquer with a math invariant, so you never explore invalid orderings.

Can Beautiful Array have multiple correct answers?

Yes. The problem asks for any beautiful permutation from 1 to n. Sample outputs are only examples, so your answer does not need to match them exactly as long as it satisfies the no-middle-average condition.

#932

Medium

auto_awesome数组·数学

LeetCode 题解工作台

漂亮数组

如果长度为 n 的数组 nums 满足下述条件，则认为该数组是一个漂亮数组： nums 是由范围 [1, n] 的整数组成的一个排列。对于每个 0 ，均不存在下标 k （ i ）使得 2 * nums[k] == nums[i] + nums[j] 。给你整数 n ，返回长度为 n 的任一 …

数组数学分治

题目描述

如果长度为 n 的数组 nums 满足下述条件，则认为该数组是一个 漂亮数组 ：

nums 是由范围 [1, n] 的整数组成的一个排列。
对于每个 0 <= i < j < n ，均不存在下标 k（i < k < j）使得 2 * nums[k] == nums[i] + nums[j] 。

给你整数 n ，返回长度为 n 的任一 漂亮数组 。本题保证对于给定的 n 至少存在一个有效答案。

示例 1 ：

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

示例 2 ：

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

提示：

1 <= n <= 1000

lightbulb

解题思路

方法一：分治

根据题意，漂亮数组 $A$ 需要满足对于任意 $i<k<j$ , $A_k*2 \neq A_i+A_j$ 。

我们可以发现，不等式左侧一定是偶数，那么我们只要保证不等式右侧 $A_i$ 和 $A_j$ 分别是一奇一偶，那么不等式就恒成立。

利用分治，我们将 $n$ 缩小规模为原来的一半，递归调用，可以得到两个漂亮数组 $left$ , $right$ 。我们将 $left$ 中每个元素 $x_i$ 变为 $x_i*2-1$ 可以得到一个奇数数组；将 $right$ 中每个元素 $x_i$ 变为 $x_i*2$ ，可以得到一个偶数数组。这两个数组仍然是漂亮数组。

基于一个性质，将漂亮数组中的每个元素 $x_i$ 变换为 $kx_i+b$ ，得到的数组仍然是漂亮数组。

将这两个漂亮数组合并在一起，由于满足一奇一偶，那么合并后的数组也是漂亮数组，从而得到了答案。

时间复杂度 $O(nlogn)$ 。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	O(N \log N)
空间	O(N \log N)

psychology

面试官常问的追问

外企场景

question_mark
They want you to stop thinking in terms of local swaps and notice a global construction based on parity.
question_mark
A strong answer explains why 2x-1 and 2x preserve beauty instead of only presenting code that seems to work.
question_mark
If they ask for n = 4 or n = 5 by hand, they are checking whether you understand the recursive build, not memorized output.

warning

常见陷阱

外企场景

error
Trying to greedily place the next number often creates a later average collision that is hard to repair.
error
Assuming you must return the sample order is wrong; Beautiful Array accepts any valid permutation.
error
Forgetting to discard mapped values greater than n will break the permutation and produce duplicates or out-of-range numbers.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return any beautiful ordering for only a subset of numbers, which keeps the same odd-even recursive idea but changes filtering.
arrow_right_alt
Count how many forbidden average triples appear in a given permutation, which flips the problem from constructive math to verification.
arrow_right_alt
Build the array iteratively with memoization versus top-down recursion, which tests whether you can preserve the same parity argument in a different implementation style.

help

常见问题

外企场景

继续练习

#973 最接近原点的 K 个点 #1569 将子数组重新排序得到同一个二叉搜索树的方案数 #927 三等分