力扣932题：利用分治策略解决“漂亮数组”

一、题目解读

LeetCode 932题要求构造长度为n的“漂亮数组”，该数组需满足：对于任意的i < j < k，不存在nums[i] + nums[k] = 2 * nums[j]。这道题考察分治算法在实际问题中的应用，需要深入理解递归与数组合并技巧。

二、解题思路分析

通过分治思想将问题分解：

1. 奇偶分离：将数组分为奇数部分和偶数部分

2. 递归构建：分别处理(n+1)/2和n/2的子问题

3. 线性组合：奇数部分通过2n-1变换，偶数部分通过2n变换

4. 数学保证：通过数论性质确保合并后的数组仍满足条件

三、具体实现步骤

1. 基准条件：当n=1时直接返回[1]

2. 递归分解：

• 奇数部分处理(n+1)/2长度

• 偶数部分处理n/2长度

3. 结果合并：

• 遍历奇数部分元素执行2x-1运算

• 遍历偶数部分元素执行2x运算

4. 返回组合：拼接处理后的奇偶数组

四、完整代码实现

class Solution {
public:
    vector<int> beautifulArray(int n) {
        // 基础情况处理
        if (n == 1) return {1};
        
        // 分治处理奇数部分和偶数部分
        vector<int> odd = beautifulArray((n + 1) / 2);  // 奇数部分
        vector<int> even = beautifulArray(n / 2);       // 偶数部分
        
        // 合并结果：奇数部分*2-1 + 偶数部分*2
        vector<int> res;
        for (int num : odd) res.push_back(num * 2 - 1);
        for (int num : even) res.push_back(num * 2);
        
        return res;
    }
};

五、算法总结

该解法通过分治策略将时间复杂度优化至O(n log n)，空间复杂度O(n log n)。关键在于发现奇偶分离的数学特性，通过线性变换保持数组的“漂亮”性质。这种思路也可应用于其他需要保持特定数学关系的排列问题。