932. Beautiful Array

// LeetCode 2020 medium #863nn// 932. Beautiful Arrayn// https://leetcode.com/problems/beautiful-array/nn// Runtime: 0 m

// LeetCode 2020 medium #863nn// 932. Beautiful Arrayn// https://leetcode.com/problems/beautiful-array/nn// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Beautiful Array.n// Memory Usage: 8.4 MB, less than 5.82% of C++ online submissions for Beautiful Array.nnclass Solution {n unordered_map<int, vector<int>> m;n npublic:n vector<int> beautifulArray(int N) {n if (N == 1) return {1};n if (m.count(N)) return m[N];n n vector<int> arr(N);n int j = 0;n auto odd = beautifulArray((N + 1) / 2);n for (int i = 0; i < odd.size(); ++i)n arr[j++] = odd[i] * 2 - 1;n auto even = beautifulArray(N - (N + 1) / 2);n for (int i = 0; i < even.size(); ++i)n arr[j++] = even[i] * 2;n m[N] = arr;n return arr;n }n};nn// Runtime: 16 ms, faster than 23.97% of C++ online submissions for Beautiful Array.n// Memory Usage: 16.2 MB, less than 5.82% of C++ online submissions for Beautiful Array.nnclass Solution {npublic:n vector<int> beautifulArray(int N) {n if (N == 1) return {1};n n vector<int> arr(N);n int j = 0;n auto odd = beautifulArray((N + 1) / 2);n for (int i = 0; i < odd.size(); ++i)n arr[j++] = odd[i] * 2 - 1;n auto even = beautifulArray(N - (N + 1) / 2);n for (int i = 0; i < even.size(); ++i)n arr[j++] = even[i] * 2;n return arr;n }n};n