資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用最多一次交換操作在 C++ 中形成最小數字
在這個問題中，我們得到一個正整數。我們的任務是建立一個程式，使用最多一次交換操作來形成較小的數字。
我們將使用現有數字的數字建立一個新數字。形成的最小數字只能交換現有數字的一個數字。
讓我們舉一個例子來理解這個問題
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
更新於: 2022年2月1日
344 次檢視
廣告