数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的美丽排列 II
假设我们有两个整数 n 和 k，我们需要构造一个列表，该列表包含 n 个不同的正整数，范围从 1 到 n，并遵循以下规则：
假设列表为 [a1, a2, a3, ... , an]，则列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 恰好有 k 个唯一的整数。因此，如果有多个答案，则显示其中任何一个。
如果输入类似于 n = 3 和 k = 2，则结果将为 [1,3,2]。[1,3,2] 包含三个不同的正整数，范围从 1 到 3。并且 [2,1] 恰好有 2 个不同的整数 1 和 2。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个数组 ret
- 对于 i := 1，j := n，检查 i <= j
- 如果 k > 1，则
- 如果 k 是奇数，则将 i 插入 ret，否则将 j 插入 ret
- 如果 k 是奇数，则将 i 增加 1，否则将 j 减小 1
- 将 k 减小 1
- 否则将 i 插入 res 并将 i 增加 1
- 如果 k > 1，则
- 返回 ret
让我们看看以下实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> constructArray(int n, int k) {
vector <int> ret;
for(int i = 1, j = n; i <= j; ){
if(k > 1){
ret.push_back(k % 2 ? i : j);
if(k % 2 == 1){
i++;
}else j--;
k--;
} else {
ret.push_back(i++);
}
}
return ret;
}
};
main(){
Solution ob;
print_vector(ob.constructArray(3, 2));
}输入
3 2
输出
[3, 1, 2, ]
更新于: 2020年5月4日
131 次查看
广告