LeetCode 932. Beautiful Array

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> ans = {1};
        while (ans.size() < n) {
            vector<int> tmp;
            for (int i : ans) if (i * 2 - 1 <= n) tmp.push_back(i * 2 - 1);
            for (int i : ans) if (i * 2 <= n) tmp.push_back(i * 2);
            ans = tmp;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    unordered_map<int, vector<int>> m;
    vector<int> beautifulArray(int n) {
        if (m.count(n)) return m[n];
        vector<int> ans(n);
        if (n == 1) ans[0] = 1;
        else {
            int i = 0;
            for (int x : beautifulArray((n + 1) / 2)) // odds.
                ans[i++] = 2 * x - 1;
            for (int x : beautifulArray(n / 2)) // evens.
                ans[i++] = 2 * x;
        }
        m[n] = ans;
        return ans;
    }
};

Reference: Odd + Even Pattern, O(N) - LeetCode Discuss