Chương trình lấy hoán vị số nguyên tiếp theo của một số trong C ++

Giả sử chúng ta có một số n, chúng ta phải tìm hoán vị lớn hơn tiếp theo của các chữ số của nó. Khi n đã ở trong hoán vị lớn nhất của nó, sau đó xoay nó xuống hoán vị nhỏ nhất.

Vì vậy, nếu đầu vào là n =319, thì đầu ra sẽ là 391.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm makeArray (), điều này sẽ lấy x,
Xác định ret mảng
trong khi x khác 0, do -
- chèn x mod 10 vào cuối ret
- x:=x / 10
đảo ngược mảng ret
trả lại ret
Xác định một hàm kết hợp (), điều này sẽ lấy một mảng v,
ret:=0
cho mỗi phần tử tôi trong v
- ret:=ret * 10
- ret:=ret + i
trả lại ret
Xác định một hàm getIndex (), điều này sẽ lấy một mảng v,
ret:=-1
để khởi tạo i:=size của v, khi i> =1, cập nhật (giảm i đi 1), thực hiện -
- nếu v [i]> v [i - 1], thì -
  - ret:=i
  - Ra khỏi vòng lặp
nếu ret không bằng -1, thì -
- x:=v [ret - 1]
- idx:=ret
- để khởi tạo j:=ret + 1, khi j
  - nếu v [j] x, thì -
    - idx:=j
- trao đổi v [ret - 1] và v [idx]
trả lại ret
Từ phương thức chính, thực hiện như sau -
Xác định một mảng v:=makeArray (num)
idx:=getIndex (v)
nếu idx giống -1, thì -
- sắp xếp mảng v
Nếu không
- sắp xếp mảng v
return kết hợp (v)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Chương trình lấy hoán vị số nguyên tiếp theo của một số trong C ++

Ví dụ

Đầu vào

Đầu ra