数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 获取下一个整数排列的程序
假设我们有一个数字 n，我们需要找到其数字的下一个更大的排列。当 n 已经是其最大排列时，则将其旋转到最小排列。
因此，如果输入像 n = 319，则输出将是 391。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 makeArray()，它将接收 x，
定义一个数组 ret
当 x 不为零时，执行：
将 x mod 10 插入 ret 的末尾
x := x / 10
反转数组 ret
返回 ret
定义一个函数 combine()，它将接收一个数组 v，
ret := 0
对于 v 中的每个元素 i
ret := ret * 10
ret := ret + i
返回 ret
定义一个函数 getIndex()，它将接收一个数组 v，
ret := -1
从 i := v 的大小开始，当 i >= 1 时，更新（i 减 1），执行：
如果 v[i] > v[i - 1]，则：
ret := i
退出循环
如果 ret 不等于 -1，则：
x := v[ret - 1]
idx := ret
从 j := ret + 1 开始，当 j < v 的大小，更新（j 加 1），执行：
如果 v[j] < v[idx] 且 v[j] > x，则：
idx := j
交换 v[ret - 1] 和 v[idx]
返回 ret
在主方法中执行以下操作：
定义一个数组 v := makeArray(num)
idx := getIndex(v)
如果 idx 等于 -1，则：
对数组 v 进行排序
否则
对数组 v 进行排序
返回 combine(v)
示例
让我们看下面的实现来更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> makeArray(int x) {
vector<int> ret;
while (x) {
ret.push_back(x % 10);
x /= 10;
}
reverse(ret.begin(), ret.end());
return ret;
}
int combine(vector<int>& v) {
int ret = 0;
for (int i : v) {
ret *= 10;
ret += i;
}
return ret;
}
int getIndex(vector& v) {
int ret = -1;
for (int i = v.size() - 1; i >= 1; i--) {
if (v[i] > v[i - 1]) {
ret = i;
break;
}
}
if (ret != -1) {
int x = v[ret - 1];
int idx = ret;
for (int j = ret + 1; j < v.size(); j++) {
if (v[j] < v[idx] && v[j] > x) {
idx = j;
}
}
swap(v[ret - 1], v[idx]);
}
return ret;
}
int solve(int num) {
vector<int> v = makeArray(num);
int idx = getIndex(v);
if(idx == -1) {
sort(v.begin(), v.end());
}
else {
sort(v.begin() + idx, v.end());
}
return combine(v);
}
};
int solve(int n) {
return (new Solution())->solve(n);
}
int main(){
int n = 319;
cout << solve(n);
}输入
319
输出
391
更新于：2020-12-22
352 次浏览
广告