找到透過插入給定數字形成的最小數字

在給定的數字中插入一個數字意味著在給定的數字中添加一個新的數字，可以是在數字的前面、後面或中間。我們已經給出了一個數字和一個數字，並且必須以盡可能小的方式將該數字添加到數字中。為了方便插入操作，我們將把數字轉換為字串。此外，給定的數字也可以是負數，因此我們必須考慮這種情況。

範例範例

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中文網其他相關文章！