一、内容

对于某些固定的 N，如果数组 A 是整数 1, 2, ..., N 组成的排列，使得：

对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。

那么数组 A 是漂亮数组。

 

给定 N，返回任意漂亮数组 A（保证存在一个）。

 

示例 1：

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

示例 2：

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

 

提示：

    1 <= N <= 1000

二、思路

• 要满足$A[k]\ast 2=A[i]+A[j]$, 最简单就是让$A[i]$是奇数，$A[j]$是偶数，这样偶数+奇数必然是奇数，而等式左边为偶数，必然不相等，于是我们可以想到让左边区间为奇数，右边区间为偶数。当n等于偶数时，左右区间元素个数相等；当n为奇数时，左边区间元素个数比右边区间多一，因为奇数会多一个。
• 如何得到左右两个区间呢，我们可以通过线性变化，经过线性变换后漂亮数组依然维持漂亮的性质。例如: A = { a , b , c } B = { 2 k ∗ a + e , 2 k ∗ b + e , 2 k ∗ c + e } A={a,b,c} B={2k * a + e, 2k*b+e, 2k*c+e } A={a,b,c}B={2k∗a+e,2k∗b+e,2k∗c+e},可以证明B也是漂亮数组，比如：$2\ast (2k\ast b+e)!=2k\ast a+e+2k\ast c+e$, 所以当我们为了得到一组漂亮数组，可以使用以前的漂亮数组合并，比如n=5, 我们可以使用n=3, n=2的漂亮数组进行合并，n=3时为{1,3,2}, n = 2时为{1, 2}, 我们只需要把左边数组变化为:2a - 1,这样就能变成奇数， 右边数组变化为:2a,得到偶数区间，2个区间直接合并便得到新的漂亮数组。通过该线性变化可以得到1~n中的所有数。
• 使用map来进行记忆化搜索节约时间

三、代码

class Solution {
public:
    unordered_map<int, vector<int>> mp; 
    vector<int> beautifulArray(int n) {
        if (n == 1) return {1};
        if (mp.count(n) != 0) return mp[n];
        vector<int> ans;
        int mid = (n + 1) / 2; //奇数情况左边区间多 右边区间个数少
        vector<int> left = beautifulArray(mid);
        vector<int> right = beautifulArray(n - mid);
        for (int i = 0; i < left.size(); i++) ans.push_back(left[i] * 2 - 1);
        for (int i = 0; i < right.size(); i++) ans.push_back(right[i] * 2);
        mp[n] = ans; //记忆化搜索
        return ans;
    }
};

最后

以上就是儒雅冬日为你收集整理的LeedCode 932. 漂亮数组一、内容二、思路三、代码的全部内容，希望文章能够帮你解决LeedCode 932. 漂亮数组一、内容二、思路三、代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。