在给定数字中插入给定数字后，找到最小的数字

在给定数字中插入数字意味着在给定数字的前面、后面或中间添加一个新的给定数字。我们给定一个数字和一个数字，并必须以使所得新数字尽可能小的方式将该数字添加到数字中。我们将数字转换为字符串以使插入操作更容易。此外，给定数字也可能是负数，因此我们必须考虑这种情况。

示例

输入1

Given number: 124
Given digit: 3
Output: 1234

说明 − 我们有四个可以添加给定数字的位置，结果可以是3124、1324、1234、1243。在这四个数字中，倒数第二个最小。

输入2

Given number: -124
Given digit: 3
Output: -3124

说明 − 我们有四个可以添加给定数字的位置，结果可以是-3124、-1324、-1234、-1243。在这四个数字中，第一个最小。

朴素方法

我们已经看到了示例，现在让我们继续看看我们将执行的解决问题的步骤：

  • 首先，我们将检查当前数字是正数还是负数。

  • 如果当前数字为负数，我们将将其标记为一个负变量，并将当前数字设为正数。

  • 之后，我们将当前数字转换为字符串，并根据当前数字是负数还是正数来调用函数。

  • 在函数中，我们将尝试将数字放在每个位置，并将根据正数或负数检查当前数字是较小还是较大。

  • 如果当前数字为正数，我们将尝试找到最小的数字并返回该数字。

  • 否则，我们将找到最大的数字，并将其乘以-1后返回。

示例

Open Compiler
#include <bits/stdc++.h>
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是给定数字中数字的个数。

高效方法

在先前的方法中，我们遍历每个数字并检查每个数字，但是高效的方法只是找到对于正数而言大于给定数字的第一个数字并将其添加并返回自身。对于负数，找到小于它的数字中的数字并将其添加并返回。

让我们看看代码：

示例

Open Compiler
#include <bits/stdc++.h>
using namespace std;
int findMin(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 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是给定数字中数字的个数。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

在本教程中，我们实现了一种方法，在给定数字中插入数字意味着在给定数字的前面、后面或中间添加一个新的给定数字。我们已经看到了两种方法，一种的时间复杂度为O(N*N)，另一种为O(N)。两种方法的空间复杂度均为O(N)。

更新于：2023年5月16日

259 次浏览

开启你的职业生涯

通过完成课程获得认证

开始
广告