LeetCode 932. 漂亮数组（分治递归/循环）
LeetCode 932. 漂亮数组（分治递归/循环）
Michael阿明
发布于 2020-07-13 14:42:03
发布于 2020-07-13 14:42:03
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
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/05/22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
