[LeetCode] 932. Beautiful Array

[grandyang]

For some fixed N, an array A is beautiful if it is a permutation of the integers 1, 2, ..., N, such that:

For every i < j, there is no k with i < k < j such that A[k] * 2 = A[i] + A[j].

Given N, return any beautiful array A.  (It is guaranteed that one exists.)

Example 1:

Input: 4
Output: [2,1,4,3]

Example 2:

Input: 5
Output: [3,1,2,5,4]

Note:

• 1 <= N <= 1000

这道题定义了一种漂亮数组，说的是在任意两个数字之间，不存在一个正好是这两个数之和的一半的数字，现在让返回长度是N的一个漂亮数组，注意这里长度是N的漂亮数组一定是由1到N之间的数字组成的，每个数字都会出现，而且一定存在这样的漂亮数组。博主刚开始时是没什么头绪的，想着总不会是要遍历所有的排列情况，然后对每个情况去验证是否是漂亮数组的吧，想想都觉得很不高效，于是就放弃挣扎，直接逛论坛了。不出意外，最高票的还是你李哥，居然提出了逆天的线性时间的解法，献上膝盖，怪不得有网友直接要 Venmo 号立马打钱，LOL～ 这道题给了提示说是要用分治法来做，但是怎么分是这道题的精髓，若只是普通的对半分，那么在 merge 的时候还是要验证是否是漂亮数组，麻烦！但若按奇偶来分的话，那就非常的叼了，因为奇数加偶数等于奇数，就不会是任何一个数字的2倍了。这就是奇偶分堆的好处，这时任意两个数字肯定不能分别从奇偶堆里取了，那可能你会问，奇数堆会不会有三个奇数打破这个规则呢？只要这个奇数堆是从一个漂亮数组按固定的规则变化而来的，就能保证一定也是漂亮数组，因为对于任意一个漂亮数组，若对每个数字都加上一个相同的数字，或者都乘上一个相同的数字，则一定还是漂亮数组，因为数字的之间的内在关系并没有改变。明白了上面这些，基本就可以解题了，假设此时已经有了一个长度为n的漂亮数组，如何将其扩大呢？可以将其中每个数字都乘以2并加1，就都会变成奇数，并且这个奇数数组还是漂亮的，然后再将每个数字都乘以2，那么都会变成偶数，并且这个偶数数组还是漂亮的，两个数组拼接起来，就会得到一个长度为 2n 的漂亮数组。就是这种思路，可以从1开始，1本身就是一个漂亮数组，然后将其扩大，注意这里要卡一个N，不能让扩大的数组长度超过N，只要在变为奇数和偶数时加个判定就行了，将不大于N的数组加入到新的数组中，参见代码如下：

class Solution {
public:
    vector<int> beautifulArray(int N) {
        vector<int> res{1};
        while (res.size() < N) {
            vector<int> t;
            for (int num : res) {
                if (num * 2 - 1 <= N) t.push_back(num * 2 - 1);
            }
            for (int num : res) {
                if (num * 2 <= N) t.push_back(num * 2);
            }
            res = t;
        }
        return res;
    }
};

Github 同步地址:

#932

参考资料：

https://leetcode.com/problems/beautiful-array/

https://leetcode.com/problems/beautiful-array/discuss/186679/Odd-%2B-Even-Pattern-O(N)

https://leetcode.com/problems/beautiful-array/discuss/187669/Share-my-O(NlogN)-C%2B%2B-solution-with-proof-and-explanation

LeetCode All in One 题目讲解汇总(持续更新中...)