数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法学在 C++ 中使用至多一次交换操作求下一更大的数
给定一个数 n，交换该数字的任意两个数字，使得结果数大于数 n。如果不可能，则打印 -1。我们来看个例子。
输入
12345
输出
12354
我们交换了数字 4 和 5。于是我们用一次交换得到一个更大的数。
算法
如果数字的各位数按降序排列，那么就不可能组成这个数。
从数的右边开始找到小于最后一位数的数字的索引。
找到大于前一位数且小于所有位数的数字的索引。
交换两个数字并返回新数字。
- 返回新数字。
实现
以下是 C++ 中上述算法的实现
#include <bits/stdc++.h>
using namespace std;
string getNextHigherNumber(string num) {
int len = num.size();
int firstDigitIndex = -1;
for (int i = len - 2; i >= 0; i--) {
if (num[i] < num[len - 1]) {
firstDigitIndex = i;
break;
}
}
if (firstDigitIndex == -1) {
return "-1";
}
int secondDigitIndex = -1;
for (int i = len - 1; i > firstDigitIndex; i--) {
if (num[i] > num[firstDigitIndex]) {
if (secondDigitIndex == -1 || num[i] <= num[secondDigitIndex]) {
secondDigitIndex = i;
}
}
}
char temp = num[firstDigitIndex];
num[firstDigitIndex] = num[secondDigitIndex];
num[secondDigitIndex] = temp;
return num;
}
int main() {
string num = "12345";
cout << "Given number: " << num << endl;
cout << "Next higher number: " << getNextHigherNumber(num) << endl;
return 0;
}输出
如果您运行上面的代码，那么您将得到以下结果。
Given number: 12345 Next higher number: 12354
更新日期： 25-Oct-2021
89 次浏览
广告