数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告