資料結構
網路
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 次瀏覽
廣告