ในปัญหานี้ เราได้รับสตริง N ที่แทนตัวเลข งานของเราคือ หาจำนวนที่มากที่สุดที่น้อยกว่า N ด้วยชุดตัวเลขเดียวกัน
คำอธิบายปัญหา: เราจำเป็นต้องค้นหาตัวเลขโดยใช้ตัวเลขทั้งหมดของตัวเลขที่ระบุซึ่งมีจำนวนน้อยที่สุดที่น้อยกว่า N
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: ไม่มี =“54314”
ผลลัพธ์: 54341
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการหาตัวเลขของตัวเลขซึ่งสามารถย้ายเพื่อหาจำนวนที่น้อยที่สุดได้ ตอนนี้ จำนวนควรจะมากกว่าความสำเร็จที่ถูกต้องเพื่อแก้ไขจุดประสงค์
สำหรับสิ่งนี้ เราจะสำรวจรูปแบบตัวเลขจากขวาไปซ้ายและค้นหาองค์ประกอบที่มากกว่าองค์ประกอบสุดท้าย
จากนั้นค้นหาองค์ประกอบที่ยิ่งใหญ่ที่สุดในอาร์เรย์ย่อยด้านขวา และแทนที่ด้วยองค์ประกอบปัจจุบัน หลังจากการเรียงลำดับ subarray จะเรียงลำดับจากมากไปน้อย นี่จะเป็นองค์ประกอบที่เล็กที่สุดของคุณ
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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;
} ผลลัพธ์
The number is 654232 The Greatest smaller number with same set of digits is 654223
