Giả sử chúng ta có một số nguyên dương 32 bit n, chúng ta cần tìm số nguyên 32 bit nhỏ nhất có đúng các chữ số giống nhau tồn tại trong số nguyên n và có giá trị lớn hơn n. Nếu chúng ta không có số nguyên dương 32 bit như vậy, thì trả về -1.
Vì vậy, nếu số là 213, thì kết quả sẽ là 231.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- s:=n dưới dạng chuỗi, sz:=kích thước của s, ok:=false
- cho tôi trong phạm vi sz - 2 đến 0
- if s [i]
- if s [i]
- nếu của là sai, thì trả về - 1
- nhỏ nhất:=i, curr:=i + 1
- cho j trong phạm vi i + 1 đến sz - 1
- id s [j]> s [nhỏ nhất] và s [j] <=s [curr], rồi đến curr:=j
- trao đổi s [nhỏ nhất] với s [curr]
- aux:=chuỗi con của s từ chỉ số 0 đến nhỏ nhất
- phụ trợ ngược
- ret:=chuỗi con của s từ chỉ số 0 đến nhỏ nhất + aux
- trả về -1 nếu ret> dải số nguyên 32 bit + ve, nếu không thì ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
int sz = s.size();
int i;
bool ok = false;
for(i = sz - 2; i >= 0; i--){
if(s[i] < s[i + 1]) {
ok = true;
break;
}
}
if(!ok) return -1;
int smallest = i;
int curr = i + 1;
for(int j = i + 1; j < sz; j++){
if(s[j] > s[smallest] && s[j] <= s[curr]){
curr = j;
}
}
swap(s[smallest], s[curr]);
string aux = s.substr(smallest + 1);
reverse(aux.begin(), aux.end());
string ret = s.substr(0, smallest + 1) + aux;
return stol(ret) > INT_MAX ? -1 : stol(ret);
}
};
main(){
Solution ob;
cout << (ob.nextGreaterElement(213));
} Đầu vào
213
Đầu ra
231