資料結構
網路
關係資料庫管理系統 (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
