หาเลขที่ใหญ่ที่สุดแต่น้อยกว่า N ที่มีหลักเดียวกันใน C++

โจทย์

ได้รับสตริง N แทนตัวเลข ทางเราต้อง หาเลขที่ใหญ่ที่สุดแต่น้อยกว่า N ที่ใช้หลักตัวเลขเดียวกัน

ตัวอย่าง

Input: N = "54314"

Output: 54341

แนวทางแก้ปัญหา

คล้ายกับ Previous Permutation:

สแกนจากขวาไปซ้าย หาตำแหน่ง i ที่ N[i] < N[i-1]
หาตัวเลขในส่วนขวาที่ น้อยกว่า N[i-1] แต่มากที่สุด
สลับ แล้วเรียงส่วนขวาแบบ Descending เพื่อให้ได้ค่ามากที่สุด

โปรแกรมตัวอย่าง

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

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

ผลลัพธ์

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