मान लीजिए कि हमारे पास एक संख्या n है, हमें इसके अंकों का अगला बड़ा क्रमचय ज्ञात करना है। जब n पहले से ही अपने सबसे बड़े क्रमपरिवर्तन में हो, तो इसे सबसे छोटे क्रमपरिवर्तन पर घुमाएँ।
इसलिए, यदि इनपुट n =319 जैसा है, तो आउटपुट 391 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन मेकअरे () को परिभाषित करें, इसमें x लगेगा,
-
एक सरणी रिट परिभाषित करें
-
जबकि x गैर-शून्य है, करें −
-
रिट के अंत में x mod 10 डालें
-
एक्स:=एक्स / 10
-
-
सरणी को उलट दें रिट
-
वापसी रिट
-
एक फ़ंक्शन कंबाइन () को परिभाषित करें, यह एक सरणी v लेगा,
-
रिट:=0
-
v में प्रत्येक तत्व के लिए
-
रिट:=रिट * 10
-
रिट:=रिट + आई
-
-
वापसी रिट
-
फ़ंक्शन को परिभाषित करें getIndex(), यह एक सरणी v लेगा,
-
रिट :=-1
-
इनिशियलाइज़ i के लिए:=v का आकार, जब i>=1, अपडेट करें (i से 1 घटाएं), करें -
-
अगर v[i]> v[i - 1], तो -
-
रिट:=मैं
-
लूप से बाहर आएं
-
-
-
अगर रिट -1 के बराबर नहीं है, तो -
-
x :=v[ret - 1]
-
आईडीएक्स:=सेवानिवृत्त
-
प्रारंभ करने के लिए j :=ret + 1, जब j
-
अगर v[j]
-
आईडीएक्स:=जे
-
-
-
एक्सचेंज v[ret - 1] और v[idx]
-
-
वापसी रिट
-
मुख्य विधि से निम्न कार्य करें -
-
एक सरणी परिभाषित करें v:=makeArray(num)
-
idx :=getIndex(v)
-
अगर idx -1 के समान है, तो -
-
सरणी को क्रमबद्ध करें v
-
-
अन्यथा
-
सरणी को क्रमबद्ध करें v
-
-
वापसी गठबंधन(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
