数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学查找包含较小和较大数字的数组中最大和最小的数字
给定一个字符串数组，每个字符串表示一个数字，该数字可能超过最大整数限制范围。我们必须从给定数组中找到最大和最小元素。我们不能使用简单的小于或大于运算符来检查哪个字符串更大，因为它不适用于字符串，因此我们将创建自己的比较函数。
示例
让我们通过一个例子来理解这个问题：
输入
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 sort 函数对其进行排序。
排序后，第一个字符串将表示最小的数字，最后一个字符串将表示最大的数字，我们将打印两者。
示例
#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(N*M*log(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)。
结论
在本教程中，我们学习了如何在给定字符串数组中查找所有数字中最小和最大的数字，其中每个字符串表示一个数字，该数字可以大于整数的范围。我们使用了两种方法：一种是使用带 O(N*M*log(N)) 时间复杂度的 STL 自定义排序函数，另一种是使用 O(N*M) 时间复杂度的另一种方法。
浏览量：111
