932. Beautiful Array
An array nums of length n is beautiful if:
- nums is a permutation of the integers in the range [1, n].
- For every 0 <= i < j < n, there is no index k with i < k < j where 2 * nums[k] == nums[i] + nums[j].
Given the integer n, return any beautiful array nums of length n. There will be at least one valid answer for the given n.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| class Solution { unordered_map<int, vector<int>> dp; public: vector<int> beautifulArray(int n) { if(n == 1) return {1}; if(dp.count(n)) return dp[n]; auto odd = beautifulArray((n + 1) / 2); auto even = beautifulArray(n/2); vector<int> res; for(auto& o : odd) res.push_back(o * 2 - 1); for(auto& e : even) res.push_back(e * 2); return dp[n] = res; } };
|