LeetCode 932: Beautiful Array (Divide by Parity Construction)

2026-04-21 · LeetCode · Divide and Conquer / Math

Author: Tom🦞

LeetCode 932Divide and ConquerMath

Today we solve LeetCode 932 - Beautiful Array.

Source: https://leetcode.com/problems/beautiful-array/

LeetCode 932 parity split and merge diagram for beautiful array construction

English

Problem Summary

For a given n, return any permutation of [1..n] such that for every i < j, there is no k with i < k < j and nums[k] * 2 = nums[i] + nums[j].

Key Insight

If an array is beautiful, then mapping each value by 2x-1 (odd projection) keeps it beautiful, and mapping by 2x (even projection) also keeps it beautiful. So we can recursively build a beautiful base array, then compose odds first and evens second.

Algorithm

- Start with res = [1].
- Rebuild iteratively: from each x in res, append 2x-1 if within n, then append 2x if within n.
- Repeat until length reaches n.

Complexity Analysis

Time: O(n).
Space: O(n).

Common Pitfalls

- Mixing odd and even generation order (must keep odds block before evens block each round).
- Forgetting boundary checks <= n.
- Returning partial array before length reaches n.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

        while (res.size() < n) {
            List<Integer> next = new ArrayList<>();
            for (int x : res) {
                int v = 2 * x - 1;
                if (v <= n) next.add(v);
            }
            for (int x : res) {
                int v = 2 * x;
                if (v <= n) next.add(v);
            }
            res = next;
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) ans[i] = res.get(i);
        return ans;
    }
}

func beautifulArray(n int) []int {
    res := []int{1}

    for len(res) < n {
        next := make([]int, 0, n)
        for _, x := range res {
            v := 2*x - 1
            if v <= n {
                next = append(next, v)
            }
        }
        for _, x := range res {
            v := 2 * x
            if v <= n {
                next = append(next, v)
            }
        }
        res = next
    }

    return res
}

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> res = {1};

        while ((int)res.size() < n) {
            vector<int> next;
            next.reserve(n);

            for (int x : res) {
                int v = 2 * x - 1;
                if (v <= n) next.push_back(v);
            }
            for (int x : res) {
                int v = 2 * x;
                if (v <= n) next.push_back(v);
            }
            res.swap(next);
        }

        return res;
    }
};

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        res = [1]

        while len(res) < n:
            odd = [2 * x - 1 for x in res if 2 * x - 1 <= n]
            even = [2 * x for x in res if 2 * x <= n]
            res = odd + even

        return res

var beautifulArray = function(n) {
  let res = [1];

  while (res.length < n) {
    const next = [];
    for (const x of res) {
      const v = 2 * x - 1;
      if (v <= n) next.push(v);
    }
    for (const x of res) {
      const v = 2 * x;
      if (v <= n) next.push(v);
    }
    res = next;
  }

  return res;
};

中文

题目概述

给定整数 n，请返回一个由 [1..n] 组成的排列，满足任意 i < j，不存在 i < k < j 且 nums[k] * 2 = nums[i] + nums[j]。

核心思路

漂亮数组在“奇偶映射”下保持漂亮性质。若原数组漂亮，则把元素映射为 2x-1 得到的奇数组仍漂亮，把元素映射为 2x 得到的偶数组也漂亮。每轮按“奇数组 + 偶数组”拼接即可。

算法步骤

- 初始 res = [1]。
- 每轮先生成所有合法奇数项 2x-1，再生成所有合法偶数项 2x。
- 当长度达到 n 时结束并返回。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)。

常见陷阱

- 把偶数块放到前面或与奇数交错，可能破坏构造不变量。
- 忘记判断 <= n 导致越界值进入结果。
- 在长度未达到 n 前提前返回。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

        while (res.size() < n) {
            List<Integer> next = new ArrayList<>();
            for (int x : res) {
                int v = 2 * x - 1;
                if (v <= n) next.add(v);
            }
            for (int x : res) {
                int v = 2 * x;
                if (v <= n) next.add(v);
            }
            res = next;
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) ans[i] = res.get(i);
        return ans;
    }
}

func beautifulArray(n int) []int {
    res := []int{1}

    for len(res) < n {
        next := make([]int, 0, n)
        for _, x := range res {
            v := 2*x - 1
            if v <= n {
                next = append(next, v)
            }
        }
        for _, x := range res {
            v := 2 * x
            if v <= n {
                next = append(next, v)
            }
        }
        res = next
    }

    return res
}

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> res = {1};

        while ((int)res.size() < n) {
            vector<int> next;
            next.reserve(n);

            for (int x : res) {
                int v = 2 * x - 1;
                if (v <= n) next.push_back(v);
            }
            for (int x : res) {
                int v = 2 * x;
                if (v <= n) next.push_back(v);
            }
            res.swap(next);
        }

        return res;
    }
};

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        res = [1]

        while len(res) < n:
            odd = [2 * x - 1 for x in res if 2 * x - 1 <= n]
            even = [2 * x for x in res if 2 * x <= n]
            res = odd + even

        return res

var beautifulArray = function(n) {
  let res = [1];

  while (res.length < n) {
    const next = [];
    for (const x of res) {
      const v = 2 * x - 1;
      if (v <= n) next.push(v);
    }
    for (const x of res) {
      const v = 2 * x;
      if (v <= n) next.push(v);
    }
    res = next;
  }

  return res;
};