ในปัญหานี้ เราได้รับจำนวนเต็มบวก งานของเราคือสร้างโปรแกรมเพื่อสร้างตัวเลขที่น้อยกว่าโดยใช้การดำเนินการสลับอย่างน้อยหนึ่งครั้ง
เราจะสร้างหมายเลขใหม่โดยใช้ตัวเลขของหมายเลขที่มีอยู่ จำนวนที่น้อยที่สุดที่เกิดขึ้นสามารถสลับจากตัวเลขที่มีอยู่ได้เพียงหลักเดียว
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input: n = 63519 Output: 36519
แนวทางการแก้ปัญหา
วิธีหนึ่งในการแก้ปัญหาคือการค้นหาตัวเลขทั้งหมดที่สร้างขึ้นโดยสลับคู่หลักของตัวเลขที่ระบุ จากตัวเลขที่สลับกันทั้งหมดเหล่านี้ ตัวเลขที่เล็กที่สุดจะถูกส่งคืน สำหรับสิ่งนี้ เราจะแปลงตัวเลขเป็นสตริงและสลับตำแหน่ง
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int findSmallestNumSwapDig(int N){
string strNum = to_string(N);
string temp = strNum;
for (int i = 0; i < strNum.size(); i++) {
for (int j = i + 1; j < strNum.size(); j++) {
swap(strNum[i], strNum[j]);
if (stoi(strNum) < stoi(temp))
temp = strNum;
swap(strNum[i], strNum[j]);
}
}
return stoi(temp);
}
int main(){
int num = 792156;
cout<<"The number is "<<num<<endl;
cout<<"The smallest number created by swapping one digit is "<<findSmallestNumSwapDig(num) << endl;
return 0;
} ผลลัพธ์
The number is 792156 The smallest number created by swapping one digit is192756
แนวทางอื่น
อีกวิธีหนึ่งในการแก้ปัญหาคือการใช้อาร์เรย์เสริมพิเศษ aux[] อาร์เรย์นี้ใช้เพื่อเก็บดัชนีของตัวเลขที่เล็กที่สุดทางด้านขวา (ดัชนีที่มากกว่า) ของดัชนีปัจจุบัน เช่น aux[i] คือดัชนีของตัวเลขที่เล็กที่สุดทางด้านขวาของหลักตัวเลข เริ่มต้น aux[i] =-1 หากไม่มีตัวเลขดังกล่าว ตอนนี้ สำรวจตัวเลขจากดัชนี 0 ถึง n-1 และค้นหาตัวเลขในอาร์เรย์ aux[] ซึ่งน้อยกว่าค่าปัจจุบัน สำหรับค่าดัชนี 0 ให้ตรวจสอบองค์ประกอบที่ไม่ใช่ศูนย์ หาก 0 เกิดขึ้น ให้ทิ้งค่านั้น หากพบองค์ประกอบใด ๆ ให้สลับ arr[i] &arr[aux[i]] และส่งคืนหมายเลขที่สร้างขึ้น
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
int findSmallestNumSwapDig(int N){
string num = to_string(N);
int n = num.size();
int auxArr[n], right;
auxArr[n - 1] = -1;
right = n - 1;
for (int i = n - 2; i >= 1; i--) {
if (num[i] >= num[right])
auxArr[i] = right;
else {
if (num[i] == num[i + 1])
auxArr[i] = right;
else {
auxArr[i] = -1;
right = i;
}
}
}
int small = -1;
for (int i = 1; i < n; i++)
if (num[i] != '0') {
if (small == -1) {
if (num[i] < num[0])
small = i;
}
else if (num[i] <= num[small])
small = i;
}
if (small != -1)
swap(num[0], num[small]);
else {
for (int i = 1; i < n; i++) {
if (auxArr[i] != -1 && num[i] != num[auxArr[i]]) {
swap(num[i], num[auxArr[i]]);
break;
}
}
}
return stoi(num);
}
int main(){
int num = 792156;
cout<<"The number is "<<num<<endl;
cout<<"The smallest number created by swapping one digit is" <<findSmallestNumSwapDig(num)<< endl;
return 0;
} ผลลัพธ์
The number is 792156 The smallest number created by swapping one digit is192756
