漂亮数组 图解题解

1 到 n 的排列，要躲开什么样的三元组

给定 n，要输出 1 到 n 的一个排列，即这 n 个数各用一次重排一遍。「漂亮」指：任取位置 i＜k＜j，中间的 nums[k] 不能是两端的平均，即不存在 2×nums[k]=nums[i]+nums[j]。题面 n=5 的答案之一是 [1, 5, 3, 2, 4]，返回任一即可。

为什么不能把排列一个个列出来验

n 的排列有 n! 个——n! 就是 1 一路乘到 n，n=5 才 120 种、n=10 已三百多万，逐个生成再用三重循环 O(n³) 验违规三元组，稍大就跑不完。得换条不靠枚举、直接拼答案的路。

奇数堆左、偶数堆右，凭什么跨中点就安全

先盯住要躲开的等式 2×nums[k]=nums[i]+nums[j]。左边 2 乘整数必是偶数，右边 nums[i]+nums[j] 也得是偶数，而两数之和为偶，当且仅当它俩同奇偶。反过来，两端一奇一偶、和为奇，就碰不上左边的偶数。

顺着这点摆出隔断：奇数全放左半、偶数全放右半。凡跨越分界的三元组，两端一个取自奇数区、一个取自偶数区，和为奇，2 倍中点是偶，绝不相等。横跨中线的三元组全排除，只剩两端同在一侧要管。

同一侧内部交给谁，映射为什么不弄丢漂亮

同侧内部的三元组，丢给规模减半的同类子问题各自去解——把大问题切成互不打架的小块，这就是分治。左半装 1 到 n 的奇数，共 ceil(n/2) 个，除不尽向上进一；右半偶数 floor(n/2) 个，除不尽向下砍。递归求 ceil(n/2) 长的漂亮排列，每个数 x→2x-1 映射成奇数；右半同理 x→2x 映射成偶数。地基 n=1，单独的 1 已漂亮。

映射为什么不弄丢漂亮？2x-1 和 2x 都是 x→ax+b 这个样子，把整组数按同比例放大、再整体挪一段；代入判定等式，常数项与公因子成对约掉后回原式，素材漂亮映射完照样漂亮。

n=5 顺着搭一遍，答案是怎么拼出来的

从地基往上搭。n=1 是 [1]；n=2 拼成 [1, 2]。n=3：奇数 2 个偶数 1 个，奇侧拿 [1, 2] 映射 2x-1 得 [1, 3]、偶侧拿 [1] 得 [2]，拼成 [1, 3, 2]。

到 n=5：奇数 3 个、偶数 2 个。奇侧素材是 [1, 3, 2]，逐个 2x-1：1 变 1、3 变 5、2 变 3，得 [1, 5, 3]。偶侧素材 [1, 2]，逐个 2x 得 [2, 4]。奇左偶右拼起来，就是 [1, 5, 3, 2, 4]。

映射配错个数，就拼不出 1 到 n 的排列

复杂度上，每层把两半映射再拼接、工作量随当前长度走，合起来 O(n)；长度每次减半、约 log n 层，总时间 O(n log n)（无备忘录，把每层 O(n) 累起来）。空间是输出和临时数组，峰值 O(n)、递归栈 O(log n)。

两处配错会拼坏答案。映射别对调：2x-1 生奇数、2x 生偶数，反了则跨中点不再安全。规模别分反：奇侧配 ceil(n/2)、偶侧配 floor(n/2)，恰是 1 到 n 里奇、偶数的个数，配错会漏数或造重复值、拼不成排列。构造已保证漂亮，不必再写三重循环验一遍。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> beautifulArray(int n) {
        if (n == 1) return {1};
        vector<int> left = beautifulArray((n + 1) >> 1);
        vector<int> right = beautifulArray(n >> 1);
        vector<int> ans(n);
        int i = 0;
        for (int& x : left) ans[i++] = x * 2 - 1;
        for (int& x : right) ans[i++] = x * 2;
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int[] beautifulArray(int n) {
        if (n == 1) {
            return new int[] {1};
        }
        int[] left = beautifulArray((n + 1) >> 1);
        int[] right = beautifulArray(n >> 1);
        int[] ans = new int[n];
        int i = 0;
        for (int x : left) {
            ans[i++] = x * 2 - 1;
        }
        for (int x : right) {
            ans[i++] = x * 2;
        }
        return ans;
    }
}