LeetCode 932. 漂亮数组（分治递归/循环）数据结构与算法Michael是个半路程序员-

1. 题目

对于某些固定的 N，如果数组 A 是整数 1, 2, …, N 组成的排列，使得：

对于每个 i < j，都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。

那么数组 A 是漂亮数组。

给定 N，返回任意漂亮数组 A（保证存在一个）。

示例 1： 输入：4 输出：[2,1,4,3]  示例 2： 输入：5 输出：[3,1,2,5,4]   提示： 1 <= N <= 1000 

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/beautiful-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

引用漂亮数组的一些性质

漂亮数组有以下的性质:

（1）A是一个漂亮数组，如果对A中所有元素添加一个常数(+b)，那么A还是一个漂亮数组。

（2）A是一个漂亮数组，如果对A中所有元素乘以一个常数(*k)，那么A还是一个漂亮数组。

（3）A是一个漂亮数组，如果删除一些A中一些元素，那么A还是一个漂亮数组。

（4）A是一个奇数构成的漂亮数组，B是一个偶数构成的漂亮数组，那么A+B也是一个漂亮数组

2.1 分治递归

class Solution { public:     vector<int> beautifulArray(int N) { if(N == 1) return {1};      vector<int> odd = beautifulArray((N+1)/2);      vector<int> even = beautifulArray(N/2);      vector<int> ans; for(int i : odd)       ans.push_back(i*2-1); for(int i : even)       ans.push_back(i*2); return ans; } }; 

28 ms 18 MB

2.2 循环

class Solution { public:     vector<int> beautifulArray(int N) {      vector<int> temp = {1}; int i, j = 0, len; while(temp.size() < N) {       len = temp.size(); for(i = 0; i < len; ++i)        temp[i] = 2*temp[i]-1; for(i = 0; i < len; ++i)        temp.push_back(temp[i]+1); }      vector<int> ans(N); for(i = 0; i < temp.size(); ++i) { if(temp[i] <= N)        ans[j++] = temp[i]; } return ans; } }; 

4 ms 7.2 MB