算法006-分治

漂亮数组

如果长度为 n 的数组 nums 满足下述条件，则认为该数组是一个漂亮数组：

nums 是由范围 [1, n] 的整数组成的一个排列。对于每个 0 <= i < j < n ，均不存在下标 k（i < k < j）使得 2 * nums[k] == nums[i] + nums[j]。给你整数 n ，返回长度为 n 的任一漂亮数组。本题保证对于给定的 n 至少存在一个有效答案。

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

提示：
1 <= n <= 1000

核心思路

核心的思路都是网上都得到的，我这里简单说明一下：
假设[a1, a2, a3, a4]是漂亮数组，那么就有[ka1+b, ka2+b, ka3+b, ka4+b]也是漂亮数组。具体如下：
要求2*nums[k] != nums[i] + nums[j]，明显左边2*nums[k]是偶数，那么要使等式不成立，就需要nums[i]和nums[j]一个偶数一个奇数。所以可以将数列基数放在left，偶数放在right。这里的奇偶不是只指[a / 2 ?== 0]，而是整体思想。
假如原始序列：[1， 2， 3， 4， 5 ... n]由奇偶性，可以分为left=[1, 3, 5, 7...]，right=[2, 4, 6, 8,...]
此时left的再分离的奇偶其实是指序列号上的奇偶，可再分为left-left=[1, 5, 9, ...]和left-right=[3, 7, 11, ...]。
由上可知，假如已经分离出来的一个数列： [b1, b2, b3, b4,...]可再次分为[b1, b3, b5,...] 和 [b2, b4, b6,...]
最终只剩下少于等于2个时，就成为一组，因为满足上式需要3个。

代码思路1

由此可抛出以下问题

问题一：如果一直将数列分为左右，多次下去，如何知道新数列的序列号？

假如[b1, b2, b3, b4,...]，很明显该数列是等差数列，即：bn - bn-1 = k，所以将其分为新的组时，就相当于分了新的序列号 b1 和 b2 = b1 + k。对于整个分割实际上类似于二叉树的分割，每次只分了两倍，所以有k = 2 * k_old。这里将序号设为t。

问题二：如何传递数列起始位置？

很明显，实际位置不是按序列号得到的，例如：[1, 2, 3, 4, 5, 6]最终分离为1, 5 | 3 | 2, 6 | 4，它的位置不是1, 2, 3, 4而是1, 3, 2, 4。
如何向下传递呢？假设当前点为p，由问题一，已知当前有k个组，序号为t，总数为n。很显然当前组分割后的left位置就是原p，而需要求right的位置，就需要知道left的个数。
虽然位置不同，但从序列号来看。前序列一定是大于等于后序列的。所以可以直接利用序列号来得出公式(n - t) % (2 * k) + 1，(n - t) % (2 * k)表示除当前原始序列号外，还有多少个。2 * k是因为要求的是分裂后的2 * k等差值，而不是现在的k等差值。

代码1

class Solution {
    void setbeautifulArray(vector<int>& nums, int t, int k, int p) {
        int n = nums.size();

        if (n < 2*k + t) {
            nums[p] = t;
            if (k + t <= n) nums[p + 1] = k + t;
        } else {
            setbeautifulArray(nums, t, 2 * k, p);
            setbeautifulArray(nums, k + t, 2 * k, p + ((n - t) / (2 * k)) + 1);
        }
    }

public:
    vector<int> beautifulArray(int n) {
        vector<int> ans(n);
        setbeautifulArray(ans, 1, 1, 0);
        return ans;
    }
};

该解法时间复杂度O(n)，空间复杂度不计入返回值O(1)。

代码思路2

已知[a1, a2, a3, a4]是漂亮数组，那么就有[ka1+b, ka2+b, ka3+b, ka4+b]也是漂亮数组。
就是有了，组A为漂亮数组，那么2A-1和2A也是漂亮数组。同时也保证2A-1和2A的和为奇数。
该写法与上不同是，一个是从底向上，一个是从顶向下。

代码2

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> ans{1};

        while (ans.size() < n) {
            vector<int> tmp;

            for (int x : ans) {
                if (2 * x - 1 <= n) tmp.push_back(2 * x - 1);
            }

            for (int x : ans) {
                if (2 * x <= n) tmp.push_back(2 * x);
            }

            ans = tmp;
        }

        return ans;
    }
};

虽然简单，但是该解法时间复杂度O(n)，空间复杂度除输出以外也是O(n)。而实际消耗甚至更大。