Medium

题目描述

长度为 n 的数组 nums 是美丽的，如果：

  • nums 是范围 [1, n] 内整数的一个排列。
  • 对于每个 0 <= i < j < n，不存在下标 k 满足 i < k < j 且 2 * nums[k] == nums[i] + nums[j]。

给你整数 n，返回任意一个长度为 n 的美丽数组 nums。题目数据保证对于给定的 n 至少存在一个有效答案。

示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 1000

解题思路

这道题的关键是理解美丽数组的性质并利用分治思想构造。

核心观察：

  1. 如果数组 A 是美丽的，那么对于任意常数 c 和 d，数组 [c*A[i] + d] 也是美丽的
  2. 奇数和偶数的和不可能是偶数，这启发我们将数组分为奇数部分和偶数部分

构造思路：

  • 对于长度为 n 的美丽数组，我们可以将其分为两部分：
    • 左半部分：所有奇数位置的元素
    • 右半部分：所有偶数位置的元素
  • 由于奇数 + 奇数 = 偶数，偶数 + 偶数 = 偶数，奇数 + 偶数 = 奇数
  • 如果我们确保左半部分都是奇数，右半部分都是偶数，那么任意三元组 (i,k,j) 中，如果 i 来自左半部分，j 来自右半部分，则 nums[i] + nums[j] 是奇数，不可能等于 2*nums[k]

递归构造：

  1. 递归构造长度为 (n+1)/2 的美丽数组作为奇数部分
  2. 递归构造长度为 n/2 的美丽数组作为偶数部分
  3. 将奇数部分映射为 2x-1（变成奇数），偶数部分映射为 2x（变成偶数）
  4. 合并两部分得到最终结果

这种方法保证了构造出的数组满足美丽数组的所有条件。

代码实现

class Solution {
public:
    vector<int> beautifulArray(int n) {
        if (n == 1) return {1};
        
        vector<int> odds = beautifulArray((n + 1) / 2);
        vector<int> evens = beautifulArray(n / 2);
        
        vector<int> result;
        
        // 添加奇数部分 (2*x - 1)
        for (int x : odds) {
            result.push_back(2 * x - 1);
        }
        
        // 添加偶数部分 (2*x)
        for (int x : evens) {
            result.push_back(2 * x);
        }
        
        return result;
    }
};

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        if n == 1:
            return [1]
        
        odds = self.beautifulArray((n + 1) // 2)
        evens = self.beautifulArray(n // 2)
        
        result = []
        
        # 添加奇数部分 (2*x - 1)
        for x in odds:
            result.append(2 * x - 1)
        
        # 添加偶数部分 (2*x)
        for x in evens:
            result.append(2 * x)
        
        return result

public class Solution {
    public int[] BeautifulArray(int n) {
        if (n == 1) return new int[] {1};
        
        int[] odds = BeautifulArray((n + 1) / 2);
        int[] evens = BeautifulArray(n / 2);
        
        int[] result = new int[n];
        int index = 0;
        
        // 添加奇数部分 (2*x - 1)
        foreach (int x in odds) {
            result[index++] = 2 * x - 1;
        }
        
        // 添加偶数部分 (2*x)
        foreach (int x in evens) {
            result[index++] = 2 * x;
        }
        
        return result;
    }
}

/**
 * @param {number} n
 * @return {number[]}
 */
var beautifulArray = function(n) {
    const memo = new Map();
    
    function helper(n) {
        if (memo.has(n)) return memo.get(n);
        
        if (n === 1) return [1];
        
        const odds = helper(Math.ceil(n / 2)).map(x => 2 * x - 1);
        const evens = helper(Math.floor(n / 2)).map(x => 2 * x);
        
        const result = odds.concat(evens);
        memo.set(n, result);
        return result;
    }
    
    return helper(n);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n) - 递归深度为 log n，每层处理 O(n) 个元素
空间复杂度O(n log n) - 递归调用栈深度为 log n，每层存储 O(n) 空间