หาตัวเลขมากกว่าที่มีหลักเดียวกันด้วย C++

ภาพรวมปัญหา

ได้รับตัวเลข N (เป็นสตริง) หาตัวเลขที่มากกว่า N น้อยที่สุดที่ใช้หลักตัวเลขชุดเดียวกัน

ตัวอย่าง

อินพุต

N = "92534"

เอาต์พุต

92543

วิธีแก้ปัญหา (Next Permutation)

1. สแกนจากขวาไปซ้าย หา index i ที่ arr[i] < arr[i+1] (จุดที่เริ่มลดลง)
2. สแกนจากขวาไปซ้าย หา index j ที่ arr[j] > arr[i] (ตัวที่มากกว่า arr[i] น้อยที่สุด)
3. Swap arr[i] และ arr[j]
4. Reverse ส่วนท้าย (i+1 ถึงสิ้นสุด) เพื่อให้เป็นลำดับน้อยที่สุด

โค้ดตัวอย่าง

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

void findNextGreater(char number[], int n) {
    int i, j;
    // หา i: ตำแหน่งที่เริ่มลดลงจากขวา
    for (i = n - 1; i > 0; i--)
        if (number[i] > number[i - 1])
            break;
    
    if (i == 0) {
        cout << "Next number is not possible";
        return;
    }
    
    // หา j: ตัวที่มากกว่า number[i-1] น้อยที่สุดทางขวา
    int x = number[i - 1], smallest = i;
    for (j = i + 1; j < n; j++)
        if (number[j] > x && number[j] < number[smallest])
            smallest = j;
    
    // Swap
    swap(number[smallest], number[i - 1]);
    
    // Sort ส่วนท้าย (reverse เพราะเดิมเป็น descending)
    sort(number + i, number + n);
    
    cout << number;
}

int main() {
    char number[] = "92534";
    int n = strlen(number);
    cout << "The next number with same set of digits is ";
    findNextGreater(number, n);
    return 0;
}

เอาต์พุต

The next number with same set of digits is 92543

สรุป

เป็นอัลกอริทึม Next Permutation มาตรฐาน Complexity O(N) ใช้ได้กับสตริงหรืออาร์เรย์