漂亮数组 图解题解

这道题到底在问什么

输入

n = 5

输出

[1, 5, 3, 2, 4]

最优解：一步一步想明白

1. 3记住这句话,后面每帧都在套它:奇数全靠左、偶数全靠右,跨中点必安全;两侧内部交给规模减半的子问题递归解决。
2. 4从最小规模起步。n=1 时只有一个数 1,孤零零一个数当然漂亮,它是整套递归的地基。后面所有更大的漂亮数组,都从它一层层搭上来。
3. 5现在搭 n=2。奇数个数是 1 个、偶数个数是 1 个,所以奇侧和偶侧都拿地基 f(1)=[1] 当素材。下面把它分别映射成「全奇」和「全偶」。
4. 6奇侧用映射 2x-1。把素材里的 1 代进去,2 乘 1 减 1 还是 1,这是一个奇数。奇侧得到 [1]。
5. 7偶侧用映射 2x。同样把 1 代进去,2 乘 1 等于 2,这是一个偶数。偶侧得到 [2]。
6. 8奇侧放左、偶侧放右,拼成 [1, 2]。这就是 f(2),存进右边的备忘录,后面更大的规模会反复取用它。
7. 9验一下:只有 1 和 2 这一对,中间根本没有别的数能当中点,自然没法违规。f(2) 漂亮,稳。
8. 10搭 n=3。1 到 3 里奇数有 2 个、偶数有 1 个,所以奇侧拿 f(2)=[1, 2],偶侧拿 f(1)=[1]。素材都已经是漂亮的,放心映射。
9. 11奇侧逐个映射。第一个素材是 1,代进 2x-1 得 1。奇侧第一格填好,先是 [1, 空]。
10. 12第二个素材是 2,代进 2x-1 得 3,又是个奇数。奇侧凑齐成 [1, 3],两个都是奇数,符合预期。
11. 13偶侧素材是 f(1)=[1],映射 2x 得 2。偶侧只有一格,就是 [2]。
12. 14奇侧 [1, 3] 放左、偶侧 [2] 放右,拼成 [1, 3, 2]。这就是 f(3),同样存进备忘录。
13. 15检验唯一的三元组:两端是 1 和 2,中点是 3。2 乘中点 3 等于 6,两端之和才 3,根本不等。f(3) 漂亮。
14. 16终于到目标 n=5。1 到 5 里奇数 3 个、偶数 2 个,奇侧拿 f(3)=[1, 3, 2],偶侧拿 f(2)=[1, 2]。两份素材备忘录里都现成,直接映射。
15. 17奇侧映射开始。素材第一个 1,代进 2x-1 得 1。奇侧先填 [1, 空, 空]。
16. 18素材第二个 3,代进 2x-1 得 5。奇侧填到 [1, 5, 空]。注意得到的都是奇数,这正是「奇侧」名字的由来。
17. 19素材第三个 2,代进 2x-1 得 3。奇侧凑齐 [1, 5, 3],三个全是奇数。左半部分搞定。
18. 20换到偶侧,素材是 f(2)=[1, 2]。第一个 1 代进 2x 得 2。偶侧先填 [2, 空]。
19. 21第二个 2 代进 2x 得 4。偶侧凑齐 [2, 4],两个都是偶数。右半部分也搞定。
20. 22奇侧 [1, 5, 3] 放左、偶侧 [2, 4] 放右,拼成 [1, 5, 3, 2, 4]。左边三个全奇、右边两个全偶,这就是 n=5 的漂亮数组。
21. 23看为什么对。只要一对位置跨过了「奇偶分界线」,左端是奇数、右端是偶数,两端之和是奇数;而 2 乘任何中点都是偶数,一奇一偶绝不可能相等。所有跨界三元组天然安全。
22. 24那同一侧内部呢?左边这三个奇数,本质就是 f(3) 做了一次 2x-1 的整体变换。这种线性变换不会破坏「漂亮」性质,而 f(3) 我们已经验过是漂亮的,所以左侧内部也安全。偶侧同理。
23. 25两块拼起来:跨界的三元组安全,各侧内部也安全,整个数组就是漂亮的。n=5 的答案锁定为 [1, 5, 3, 2, 4]。题目允许任一漂亮数组,这一个就行。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问