LeetCode 932. 漂亮数组

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 数学 分治

题目描述

✅ 932. 漂亮数组

image-20260929105246962

题意分析

构造 1 到 n 的一个排列，使任意 i<k<j 都满足 2*A[k] != A[i]+A[j]。限制针对任意跨度的三个位置，不只是相邻元素；只要给出一个合法排列即可。

直接逐个选择元素很难维护所有三元组约束，可以从较小的合法数组出发，用保持这个性质的变换不断扩大。

解法：分治构造（奇数部分 + 偶数部分）

核心思路

[!blue]

先把所有奇数排成连续一块，再把所有偶数排成连续一块。对任意左右端点，若它们属于不同块，数值之和为奇数，不可能等于某个整数的两倍；若属于同一块，中间下标也一定在该块内。因此只要每块内部合法，拼接后整个数组就合法。

若旧数组已经漂亮，把每个值 x 同时换成 2x-1，得到的奇数块仍然漂亮：新数组若出现等式，将两边的倍数与常数消去，就会得到旧数组中同样的等差等式，与假设矛盾。偶数映射 2x 也同理。两次映射都保留旧元素的相对顺序，所以可以直接作为两块内部的排列。

从只有一个元素的 [1] 开始，每轮按旧顺序生成全部奇数，再生成全部偶数，并丢弃超过 n 的值。删除元素只会保留原顺序中的部分位置；若剩下的元素出现违规三元组，它在删除前也已经存在，因此过滤不会破坏漂亮性。

还要保证结果确实是完整排列。若旧数组恰好包含 1..m 各一次，奇数与偶数映射分别覆盖 1..2m 中的奇数和偶数，块内没有重复，两块也不相交；过滤后恰好得到 1..min(2m,n)。所以元素数量逐轮翻倍，最后达到 n，既不漏数也不重复，构造一定结束。

解题步骤

  1. 以 [1] 为构造起点。
  2. 按旧顺序生成不超过 n 的所有 2x-1。
  3. 再按旧顺序生成不超过 n 的所有 2x。
  4. 替换为新数组，直到包含 n 个数。

n=1 时初始数组已经是答案。其余情况下每轮都必须完整生成奇数块后再生成偶数块，不能把两种映射交替写入，否则跨块端点的奇偶证明就不再适用。

代码实现

class Solution {
    public int[] beautifulArray(int n) {
        List<Integer> res = new ArrayList<>();

        res.add(1);

        while (res.size() < n) {
            List<Integer> tmp = new ArrayList<>(n);

            for (int x : res) {
                // 先按原顺序生成整块奇数，仿射变换保持原有漂亮性。
                int v = 2 * x - 1;

                if (v <= n) {
                    tmp.add(v);
                }
            }

            for (int x : res) {
                // 再生成整块偶数，跨块端点一奇一偶，不会形成整数平均。
                int v = 2 * x;

                if (v <= n) {
                    tmp.add(v);
                }
            }

            res = tmp;
        }

        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            answer[i] = res.get(i);
        }

        return answer;
    }
}

func beautifulArray(n int) []int {
    res := []int{
        1,
    }
    for len(res) < n {
        tmp := make([]int, 0, n)
        for _, x := range res {
            // 先按原顺序生成整块奇数，仿射变换保持原有漂亮性。
            v := 2*x - 1
            if v <= n {
                tmp = append(tmp, v)
            }
        }
        for _, x := range res {
            // 再生成整块偶数，跨块端点一奇一偶，不会形成整数平均。
            v := 2 * x
            if v <= n {
                tmp = append(tmp, v)
            }
        }
        res = tmp
    }
    return res
}

复杂度分析

  • 时间复杂度：各轮有效长度按倍数增长，映射扫描总量为 $O(n)$；当前实现每轮都预分配容量 n，共有 $O(\log(n+1))$ 轮，计入分配初始化后的上界为 $O(n\log(n+1))$。
  • 空间复杂度：$O(n)$，同时保存前后两轮数组。

关键点总结

[!green]

  • 奇偶分块负责消除跨块冲突，保持等差关系的映射负责保证块内合法。
  • 覆盖范围每轮从 1..m 扩大到 1..min(2m,n)，保证构造完整且终止。
  • 过滤只删除元素并保留顺序，不会产生新的违规三元组。

易错点总结

[!yellow]

  • 不能只保证所有值互不相同，还要保持奇偶连续分块和块内原有顺序。
  • 奇数映射必须是 2x-1，写成 2x+1 会漏掉数字 1。
  • 生成时过滤大于 n 的值，长度达到 n 后立即结束。

相似题目

题目 难度 关联与区别
1968. 构造元素不等于两相邻元素平均值的数组 中等 原题只禁止相邻三项出现中间等于两侧平均，本题禁止任意跨度的三项，需更强的奇偶分治构造。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/78944750
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！