932. Beautiful Array

题解

本题属于构造类题目，构造类题目通常比较难。。。属于脑筋急转弯类型。
对于本题来说，如果一个数组{a1, a2, …, an}是漂亮数组，那么{ta1 + b, ta2 + b, …, tan +b}也是漂亮数组。
所以我们递归构造，我们把数组分为两部分，假设左半边可以得到一个漂亮数组，右半边可以得到一个漂亮数组。因此我们只需要使得当i在左边，j在右边，中间的所有元素k，不满足nums[k] 2 != nums[i] + nums[j]。
我们令左边的数=2x - 1，右边的数是2 x，这样左边一个数加上右边一个数，一定是奇数，所以不存在nums[k] 2 != nums[i] + nums[j]的情况。

代码

  1. class Solution {
  2. public:
  3.     vector<int> beautifulArray(int n) {
  4.         if (n == 1) return {1};
  5.         auto left = beautifulArray((n + 1) / 2);
  6.         auto right = beautifulArray(n / 2);
  7.         vector<int> res;
  8.         for (auto x: left) {
  9.             res.push_back(2 * x - 1);
  10.         }
  11.         cout << endl;
  12.         for (auto x: right) {
  13.             res.push_back(2 * x);
  14.         }
  15.         return res;
  16.     }
  17. };