ในปัญหานี้ เราได้รับจำนวนเต็มบวก ภารกิจของเราคือการสร้างโปรแกรมสร้างตัวเลขที่น้อยกว่าโดยใช้การสลับได้สูงสุดหนึ่งครั้ง
เราจะสร้างตัวเลขใหม่โดยใช้หลักของตัวเลขที่มีอยู่ ตัวเลขที่น้อยที่สุดที่สร้างได้สามารถมีได้เพียงหนึ่งหลักที่สลับจากตัวเลขที่มีอยู่
มาดูตัวอย่างเพื่อเข้าใจปัญหา
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
