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

Mô tả bài toán

Cho số nguyên n, tìm hoán vị tiếp theo lớn hơn của các chữ số. Nếu đã là hoán vị lớn nhất thì quay về hoán vị nhỏ nhất (sắp xếp tăng).

Ví dụ: n=319 → 391.

Giải thuật

1. Chuyển số thành mảng chữ số.
2. Tìm chỉ số i từ phải sang trái sao cho a[i] > a[i-1].
3. Nếu không tìm thấy (i=-1): sắp xếp mảng tăng dần.
4. Ngược lại: tìm chỉ số j từ i đến cuối sao cho a[j] là giá trị nhỏ nhất > a[i-1]. Hoán vị a[i-1] và a[j]. Sắp xếp đoạn từ i đến cuối tăng dần.
5. Ghép mảng thành số.

Ví dụ minh họa (C++)

#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 d : v) { ret = ret*10 + d; }
        return ret;
    }
    int getIndex(vector<int>& v) {
        int idx = -1;
        for (int i = v.size()-1; i >= 1; i--)
            if (v[i] > v[i-1]) { idx = i; break; }
        if (idx != -1) {
            int x = v[idx-1], best = idx;
            for (int j = idx+1; j < v.size(); j++)
                if (v[j] < v[best] && v[j] > x) best = j;
            swap(v[idx-1], v[best]);
        }
        return idx;
    }
    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);
    return 0;
}

Đầu vào

319

Đầu ra

391