力扣932题：利用分治算法和质数特性完美解决

一、题目解读

力扣932题要求生成一个长度为n的，由正整数组成的数组，其中任意相邻元素的和均为质数。例如，n=5时，数组[1,4,2,3,5]满足条件，因为1+4=5、4+2=6、2+3=5、3+5=8均为质数。题目需设计高效算法，避免暴力枚举所有组合，需利用数学性质或分治策略优化。

二、解题思路

采用分治算法，结合质数的数学特性，将问题分解为奇数和偶数两部分递归求解。核心思想：

1. 基础情况：当n=1时，直接返回[1]。

2. 分治递归：

○ 若n为奇数，递归生成长度为(n+1)/2的奇数部分数组，每个元素乘以2后减1；

○ 若n为偶数，递归生成长度为n/2的偶数部分数组，每个元素乘以2。

3. 合并两部分结果，保证相邻元素和为质数。

关键在于利用质数的分布规律：奇数与偶数乘积为奇数（质数候选），且通过分治减少重复计算。

三、解题步骤

1. 基础情况处理：若n=1，返回单元素数组{1}。

2. 分治递归：

○ 当n为奇数时，递归生成奇数部分beautifulArray((n+1)/2)，每个元素num变为num*2-1（例如，[1,3] → [12-1,32-1] = [1,5]）。

○ 当n为偶数时，递归生成偶数部分beautifulArray(n/2)，每个元素num变为num*2（例如，[2,4] → [22,42] = [4,8]）。

3. 合并结果：将奇数部分与偶数部分交替拼接，形成最终数组。

4. 验证质数条件：由于奇数2-1与偶数2的相邻和均为奇数（可能质数），且递归生成的子数组已满足条件，合并后自然满足题目要求。

四、代码与注释

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

注释说明：

● if (n == 1)：基础情况避免递归栈溢出；

● (n + 1) / 2：当n为奇数时，确保奇数部分长度正确（例如，n=5时生成长度为3的奇数部分）；

● 合并时交替添加奇偶部分元素，保证相邻元素和为奇数，利用质数多为奇数的特性。

五、总结

本文通过分治算法与质数特性，将问题分解为更易处理的奇偶子问题，递归构建Beautiful Array。核心优势在于：

1. 利用数学规律（偶数2与奇数2-1的和为奇数）确保质数条件；

2. 分治减少重复计算，时间复杂度O(nlogn)，空间复杂度O(logn)（递归栈）；

3. 代码简洁且无需额外质数判断，为典型数学+分治结合的优化解法。

适用于需高效生成符合特定数学规律的数组场景，适合算法竞赛与数学思维训练。