C++ 在包含小数和大数的数组中找到最大和最小的数

给定一个字符串数组，每个字符串表示一个可能超过最大整数限制范围的数字。我们需要找出给定数组中的最大和最小元素。我们不能使用简单的小于或大于运算符来检查哪个字符串更大，因为它不能正确处理字符串，所以我们将自己定义比较函数。

示例

让我们通过一个例子来理解这个问题 –

输入

string arr[] = {"2", "3", "12", "23", "22", "0", "7"}

输出

The smallest element in the given array is: 0
The largest element in the given array is: 23

排序方法

在这种方法中，我们将使用STL排序函数对给定的字符串进行排序，并使用我们定义的额外比较函数。

• 首先，我们将创建一个函数，它将比较两个字符串，并返回第一个字符串（表示一个数字）是否比另一个字符串小，不是按照字典顺序，而是按照数字顺序。

• 我们将创建另一个函数，在该函数中，我们将传递给定的数组，并使用上述创建的比较函数使用STL排序函数对其进行排序。

• 在排序后，第一个字符串将表示最小的数字，最后一个字符串将表示最大的数字，我们将打印它们。

示例

#include <bits/stdc++.h>
using namespace std;

// comparision function 
bool cmp(string& a, string& b){
   if(a.size() == b.size()){
      return a < b;
   } else {
      return a.size() < b.size();
   }   
}
void getValue(vector<string> arr){
   int len = arr.size(); // getting size of the array     
   // sorting the given array 
   sort(arr.begin(), arr.end(), cmp);    
   // first element is the smallest 
   cout<<"The smallest element in the given array is: " << arr[0]<<endl;    
   // last element is the largest 
   cout<<"The largest element in the given array is: " << arr[len-1]<<endl;
}
int main(){
   // given array 
   vector<string> arr = { "2", "3", "12", "23", "22", "0", "7"};
   // calling to the required function 
   getValue(arr);
   return 0;
}

输出

The smallest element in the given array is: 0
The largest element in the given array is: 23

时间和空间复杂度

以上代码的时间复杂度为O(NMlog(N))，其中N是数组中给定元素的数量，M是给定数字的最大大小，对数因子是由于排序操作。

以上代码的空间复杂度为O(1)或常量，因为在以上代码中没有使用任何额外的空间。

比较方法

在这种方法中，我们将维护两个变量，它们都包含给定数组的第一个元素，并且我们将使用这两个变量与给定数组中的每个元素进行比较，以获取给定数字中的最小和最大数。

我们将为在字符串形式下的数字之间的比较创建一个函数，该函数使用我们在先前代码中用于比较的比较函数。

通过遍历数组，我们将获得所需的字符串，并在同一函数中打印它们。

示例

#include <bits/stdc++.h>
using namespace std;

// comparision function 
bool isSmall(string& a, string& b){
   if(a.size() == b.size()){
      return a < b;
   } else {
      return a.size() < b.size();
   }   
}
void getValue(vector<string> arr){
   int len = arr.size(); // getting size of the array     
   // variable to store the current smallest number 
   string cur = arr[0];    
   // traversing over the array 
   for(int i=1; i<len; i++){
      if(isSmall(cur, arr[i]) == false){
         cur = arr[i];
      }
   }
   // printing the smallest element in the given array 
   cout<<"The smallest element in the given array is: " << cur<<endl;    
   // updating the value of cur to first 
   // now it will store the largest value 
   cur = arr[0];    
   // traversing over the array 
   for(int i=1; i<len; i++){
      if(isSmall(cur, arr[i])){
         cur = arr[i];
      }
   }    
   // printing the largest element in the given array 
   cout<<"The largest element in the given array is: " << cur <<endl;
}
int main(){
   // given array 
   vector<string> arr   = { "2", "3", "12", "23", "22", "0", "7"};
   // calling to the required function 
   getValue(arr);
   return 0;
}

输出

The smallest element in the given array is: 0
The largest element in the given array is: 23

时间和空间复杂度

我们只需对数组进行两次遍历或线性遍历，并且对于每次比较，我们都会获得更多的线性时间，所以时间复杂度为O(N*M)，其中N是给定数组的大小，M是最大数字的大小。

我们在这里使用了额外的空间，使空间复杂度因子为最大整数的大小O(M)。

结论

在本教程中，我们学习了如何在给定的字符串数组中找到最小值和最大值，其中每个字符串都表示一个大于整数范围的数字。我们使用了两种方法：使用STL自定义排序函数的时间复杂度为O(NMlog(N))，另一种方法的时间复杂度为O(N*M)。