题目描述

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

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

那么数组 A 是漂亮数组。

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

样例

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

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

注意

• 1 <= N <= 1000

算法

(分治) $\Theta(n \log n)$

1. 对于一个连续的数列 $1,2,3,…,n$，如果按照奇偶分成两部分，$1,3,5,…$ 放到左边，$2,4,6,8,…$ 放到右边。这样重新安排后，如果 $i$ 属于左边，$j$ 属于右边，$A[i]+A[j]$ 就必定是奇数，因而不存在 $A[k]$，满足 $A[k]*2=A[i] + A[j]$。
2. 接下来再看每一部分的内部，由于 $1,3,5,…$ 也是等差数列，所以可以经过变换再次变成 $1,2,3,…$，且变换后的数列如果满足题目的性质，则原数列同样满足。如果我们仍然按照 1 中的策略进行奇偶分离，则可以继续分为两部分递归处理。同理 $2,4,6,…$ 也可以进行变换然后递归。
3. 最后递归的出口是仅有一个数字时，直接返回。
4. 实际上，不需要显式的进行变换，只需要在每一次递归时，将当前数组中，位于奇数位置的数字按原顺序放到前边，之后放置位于偶数位置的数字按原顺序，然后递归即可。

时间复杂度

• 每一层的时间复杂度为 $\Theta(n)$，一共有 $\log n$ 层，故总时间复杂度为 $\Theta(n \log n)$。

C++ 代码

class Solution {
public:

    void solve(int l, int r, vector<int> &ans) {
        if (l == r)
            return;

        vector<int> tmp(r - l + 1);
        int cnt = 0;

        for (int i = l; i <= r; i += 2)
            tmp[cnt++] = ans[i];
        for (int i = l + 1; i <= r; i += 2)
            tmp[cnt++] = ans[i];

        for (int i = l; i <= r; i++)
            ans[i] = tmp[i - l];

        int mid = (l + r) / 2;
        solve(l, mid, ans);
        solve(mid + 1, r, ans);
    }

    vector<int> beautifulArray(int N) {
        vector<int> ans(N);
        for (int i = 0; i < N; i++)
            ans[i] = i + 1;
        solve(0, N - 1, ans);
        return ans;
    }
};