[LeetCode] 932. Beautiful Array 漂亮數組

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

with

i < k < j

such that

A[k] * 2 = A[i] + A[j]

Given

, return any beautiful array

. (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)

喜歡請點贊，疼愛請打賞❤️~.~

微信打賞

Venmo 打賞