Tạo số lớn nhất bằng tối đa một lần hoán đổi chữ số C++

Mô tả bài toán

Cho số nguyên dương. Hoán đổi tối đa một cặp chữ số để tạo số lớn nhất có thể.

Ví dụ

n=63512 → Output: 65312 (hoán đổi 3 và 5).

Giải thuật

• Cách 1 O(L²): Thử mọi cặp, lấy max.
• Cách 2 O(L): Duyệt từ phải sang trái, theo dõi chữ số lớn nhất gặp phải (maxDig, maxIdx). Nếu chữ số hiện tại < maxDig → ghi nhớ cặp hoán đổi (i, maxIdx). Cuối cùng hoán đổi cặp ghi nhớ cuối cùng (cặp trái nhất có lợi).

Mã nguồn C++ (Cách 2)

#include <iostream>
using namespace std;

int findLargestNumSwapDig(int N) {
    string s = to_string(N);
    int maxDig=-1, maxIdx=-1, lSwap=-1, rSwap=-1;
    for (int i=s.size()-1; i>=0; i--) {
        if (s[i] > maxDig) { maxDig=s[i]; maxIdx=i; continue; }
        if (s[i] < maxDig) { lSwap=i; rSwap=maxIdx; }
    }
    if (lSwap==-1) return N;
    swap(s[lSwap], s[rSwap]);
    return stoi(s);
}

int main() {
    int num=792156;
    cout << "Largest after one swap: " << findLargestNumSwapDig(num);
    return 0;
}

Đầu ra

The largest number created by swapping one digit is 972156