Cho một số n, hoán đổi hai chữ số bất kỳ của số đó để số thu được lớn hơn số n. Nếu không thể, hãy in -1. Hãy xem một ví dụ.
Đầu vào
12345
Đầu ra
12354
Chúng tôi đã hoán đổi các chữ số 4 và 5. Và chúng tôi nhận được số cao hơn với một lần hoán đổi.
Thuật toán
-
Không thể tạo số nếu các chữ số của số theo thứ tự giảm dần.
-
Tìm chỉ số của chữ số ở bên phải của số nhỏ hơn chữ số cuối cùng.
-
Tìm chỉ số của chữ số lớn hơn chữ số trước và nhỏ hơn tất cả các chữ số.
-
Hoán đổi hai chữ số và trả lại số mới.
- Trả lại số mới.
Thực hiện
Sau đây là cách thực hiện thuật toán trên trong 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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
Given number: 12345 Next higher number: 12354