数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时装设计
法律研究寻找具有 n 个峰值的排列的 C++ 程序
假设我们有两个数字 n 和 k。我们必须使用从 1 到 n 的数字构造一个排列 A，而后者恰好有 k 个峰值。如果 A[i] > A[i-1] 且 A[i] > A[i+1]，则称数组 A 的索引 i 为峰值。如果这是不可能的，则返回 -1。
因此，如果输入类似于 n = 5； k = 2，则输出将为 [2, 4, 1, 5, 3]，其他答案也是可能的。
步骤
要解决此问题，我们将按照以下步骤进行操作 -
if k > (n - 1) / 2, then: return -1 Define an array a of size: 101. for initialize i := 1, when i <= n, update (increase i by 1), do: a[i] := i for initialize i := 2, when i <= 2 * k, update i := i + 2, do: swap a[i] and a[i + 1] for initialize i := 1, when i <= n, update (increase i by 1), do: print a[i]
示例
让我们看看以下实现以获得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
void solve(int n, int k) {
if (k > (n - 1) / 2) {
cout << "-1";
return;
}
int a[101];
for (int i = 1; i <= n; i++)
a[i] = i;
for (int i = 2; i <= 2 * k; i += 2) {
swap(a[i], a[i + 1]);
}
for (int i = 1; i <= n; i++)
cout << a[i] << ", ";
}
int main() {
int n = 5;
int k = 2;
solve(n, k);
}输入
5, 2
输出
1, 3, 2, 5, 4,
更新于:03 年 3 月 2022 日
221 次浏览
宣传