ตัวเลขถัดไปที่มากกว่าโดยใช้การสลับได้สูงสุด 1 ครั้งใน C++

โจทย์

ได้รับตัวเลข n สลับสองหลักใดๆ ของตัวเลขเพื่อให้ตัวเลขที่ได้มากกว่า n หากไม่เป็นไปได้ให้พิมพ์ -1 มาดูตัวอย่างกัน

อินพุต

12345

เอาต์พุต

12354

เราสลับหลัก 4 และ 5 และได้ตัวเลขที่มากกว่าด้วยการสลับครั้งเดียว

อัลกอริธึม

• ไม่สามารถสร้างตัวเลขได้ถ้าหลักของตัวเลขเรียงลำดับลดลง
• หาดัชนีของหลักจากขวาของตัวเลขที่น้อยกว่าหลักสุดท้าย
• หาดัชนีของหลักที่มากกว่าหลักก่อนหน้าและน้อยกว่าหลักทั้งหมด
• สลับสองหลักและคืนค่าตัวเลขใหม่
• คืนค่าตัวเลขใหม่

การนำไปใช้งาน

ต่อไปนี้เป็นการนำไปใช้งานของอัลกอริธึมข้างต้นใน C++

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

string getNextHigherNumber(string num) { 
    int len = num.size(); 
    int firstDigitIndex = -1; 
    for (int i = len - 2; i >= 0; i--) { 
        if (num[i] < num[len - 1]) { 
            firstDigitIndex = i; 
            break; 
        } 
    } 
    if (firstDigitIndex == -1) { 
        return "-1"; 
    } 
    int secondDigitIndex = -1; 
    for (int i = len - 1; i > firstDigitIndex; i--) { 
        if (num[i] > num[firstDigitIndex]) { 
            if (secondDigitIndex == -1 || num[i] <= num[secondDigitIndex]) { 
                secondDigitIndex = i; 
            } 
        } 
    } 
    char temp = num[firstDigitIndex]; 
    num[firstDigitIndex] = num[secondDigitIndex]; 
    num[secondDigitIndex] = temp; 
    return num; 
} 

int main() { 
    string num = "12345"; 
    cout << "Given number: " << num << endl; 
    cout << "Next higher number: " << getNextHigherNumber(num) << endl; 
    return 0; 
}

ผลลัพธ์

หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้

Given number: 12345
Next higher number: 12354