Tìm số lớn nhất nhỏ hơn N với cùng tập chữ số trong C++

Cho chuỗi N biểu diễn một số. Nhiệm vụ: tìm số lớn nhất nhỏ hơn N dùng cùng tập chữ số.

Mô tả: Tìm số hoán vị của N lớn nhất nhưng nhỏ hơn N.

Ví dụ:

Đầu vào: N = "54314"

Đầu ra: 54341

Phương pháp giải

Duyệt từ phải sang trái tìm cặp chữ số giảm dần (a[i] < a[i-1]). Tìm chữ số lớn nhất bên phải nhỏ hơn a[i-1], hoán đổi, sau đó sắp xếp phần đuôi giảm dần.

Chương trình minh họa

Ví dụ

#include <bits/stdc++.h>
using namespace std;

void calcGreatestSmallerElement(string N, int size) {
    int i, j;
    for (i = size - 1; i > 0; i--)
        if (N[i] < N[i - 1])
            break;
    if (i == 0) {
        cout << "Previous number is not possible";
        return;
    }
    int x = N[i - 1], greatest = i;
    for (j = i; j < size; j++)
        if (N[j] < x && N[j] > N[greatest])
            greatest = j;
    swap(N[greatest], N[i - 1]);
    sort(N.begin() + i, N.begin() + size, greater<char>());
    cout << "The Greatest smaller number with same set of digits is " << N;
    return;
}

int main() {
    string N = "654232";
    int size = N.length();
    cout << "The number is " << N << endl;
    calcGreatestSmallerElement(N, size);
    return 0;
}

Kết quả

The number is 654232 The Greatest smaller number with same set of digits is 654223