在给定的数字中插入一个数字意味着在给定的数字中添加一个新的数字，可以是在数字的前面、后面或者中间。我们已经给出了一个数字和一个数字，并且必须以尽可能小的方式将该数字添加到数字中。为了方便插入操作，我们将把数字转换为字符串。此外，给定的数字也可以是负数，因此我们必须考虑这种情况。
示例示例
Input1
的中文翻译为：
输入1
Given number: 124Given digit: 3Output: 1234
Explanation − 我们有四个地方可以添加给定的数字，结果可以是3124、1324、1234、1243。在这四个中，倒数第二个是最小的。
Input2
的中文翻译为：
输入2
Given number: -124Given digit: 3Output: -3124
Explanation − 我们有四个地方可以添加给定的数字，结果可以是-3124，-1324，-1234，-1243。在这四个中，第一个是最小的。
Naive Approach
的中文翻译为：
天真的方法
我们现在已经看过了示例，接下来让我们看一下我们将执行的解决问题的步骤 –
首先，我们将检查当前数字是正数还是负数。
如果当前数字为负数，我们将将其标记为负数变量，并将当前数字设为正数。
之后，我们将把当前的数字转换为字符串，并根据当前数字的正负调用函数basis。
在这些函数中，我们将尝试在每个位置上适配数字，并根据正数或负数来检查当前数字是较小还是较大。
如果当前数字是正数，我们将尝试找到最小的数字并返回。
否则，我们将找到最大的数字，并通过乘以-1来返回它。
Example
的中文翻译为：
示例
#include using namespace std;int findMin(string str, int d){ string ans = str + to_string(d); // variable to store the answer // traversing over the string for(int i=0; i<= str.size(); i++){ ans = min(ans, str.substr(0,i) + to_string(d) + str.substr(i)); } return stoi(ans);}int findMax(string str, int d){ string ans = str + to_string(d); // variable to store the answer // traversing over the string for(int i=0; i<= str.size(); i++){ ans = max(ans, str.substr(0,i) + to_string(d) + str.substr(i)); } return stoi(ans);}int minimumNumber(int n, int d){ // checking for the negative number int isNeg = 1; if(n < 0){ n *= -1; isNeg = -1; } // converting the current number to string string str = to_string(n); if(isNeg == 1){ return findMin(str,d); } else{ return -1*findMax(str,d); }}int main(){ int n = -124; // given number int d = 3; // given digit // calling to the function n = minimumNumber(n, d); cout<<"The minimum number after adding the new digit is "<<n<<endl; return 0;}
输出
The minimum number after adding the new digit is -3124
时间和空间复杂度
上述代码的时间复杂度为O(N*N)，其中N是给定数字的位数。
上述代码的空间复杂度为O(N)，其中N是给定数字的位数。
高效的方法
在之前的方法中，我们一直在检查每个数字，找到比给定数字大的第一个数字，然后将其添加并返回自身，这是一种高效的方法。对于负数，找到比它小的数字，并将其添加并返回。
让我们看看代码−
Example
的中文翻译为：
示例
#include using namespace std;int findMin(string str, int d){ // traversing over the string for(int i=0; i d){ return stoi(str.substr(0,i) + to_string(d) + str.substr(i)); } } return stoi(str + to_string(d));}int findMax(string str, int d){ // traversing over the string for(int i=0; i<= str.size(); i++){ if(str[i]-'0' < d){ return stoi(str.substr(0,i) + to_string(d) + str.substr(i)); } } return stoi(str + to_string(d));}int minimumNumber(int n, int d){ // checking for the negative number int isNeg = 1; if(n < 0){ n *= -1; isNeg = -1; } // converting the current number to string string str = to_string(n); if(isNeg == 1){ return findMin(str,d); } else{ return -1*findMax(str,d); }}int main(){ int n = 124; // given number int d = 3; // given digit // calling to the function n = minimumNumber(n, d); cout<<"The minimum number after adding the new digit is "<<n<<endl; return 0;}
输出
The minimum number after adding the new digit is 1234
时间和空间复杂度
上述代码的时间复杂度为O(N)，其中N是给定数字的位数。
上述代码的空间复杂度为O(N)，其中N是给定数字的位数。
结论
在本教程中，我们实现了一种在给定数字中插入数字的方法，即在给定数字的前面、后面或数字之间添加一个新的给定数字。我们看到了两种方法，一种时间复杂度为O(N*N)，另一种为O(N)。这两种方法的空间复杂度都是O(N)。
以上就是找到通过插入给定数字形成的最小数字的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444690.html
微信扫一扫 
支付宝扫一扫 
