找到通过插入给定数字形成的最小数字

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

示例示例

Input1

的中文翻译为：

输入1

Given number: 124
Given digit: 3
Output: 1234 

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

Input2

的中文翻译为：

输入2

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

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

Naive Approach

的中文翻译为：

天真的方法

我们现在已经看过了示例，接下来让我们看一下我们将执行的解决问题的步骤 -

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

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

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

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

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

• 否则，我们将找到最大的数字，并通过乘以-1来返回它。

Example

的中文翻译为：

示例

#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是给定数字的位数。

高效的方法

在之前的方法中，我们一直在检查每个数字，找到比给定数字大的第一个数字，然后将其添加并返回自身，这是一种高效的方法。对于负数，找到比它小的数字，并将其添加并返回。

让我们看看代码−

Example

的中文翻译为：

示例

#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是给定数字的位数。

结论

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

以上是找到通过插入给定数字形成的最小数字的详细内容。更多信息请关注PHP中文网其他相关文章！