[LeetCode] 932. Beautiful Array 漂亮数组

时间:2022-02-16 01:12:06

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中...)](https://www.cnblogs.com/grandyang/p/4606334.html)