資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的陣列最小-最大範圍查詢
給定一個包含 N 個元素的陣列 Arr[]。目標是從查詢的索引中找到最小值和最大值。
根據查詢，我們給定起始索引和結束索引。
例如
輸入 - Arr[] = { 1, 2, 3, 4, 5 } QStart = 1 QEnd = 4
輸出 -
最小值：2
最大值：5
解釋 - 在上述查詢中，起始索引為 1，結束索引為 4。在這兩個索引之間，Arr 中的最小值為 2，最大值為 5
輸入 - Arr[] = { 10, 12, 3, 2, 5, 18 } QStart = 2 QEnd = 5
輸出 -
最小值：2
最大值：18
解釋 - 在上述查詢中，起始索引為 2，結束索引為 5。在這兩個索引之間，Arr 中的最小值為 2，最大值為 18
下面程式中使用的方案如下：
在這種方案中，我們將使用線段樹來查詢給定查詢範圍內的最小值和最大值，範圍從 lpos 到 rpos。
獲取輸入陣列 Arr[] 和查詢索引 QStart 和 QEnd。
獲取 value 型別的結果。
結構體 value 用於使用給定查詢儲存陣列中找到的最小值和最大值。
結構體 value 用於使用給定查詢儲存陣列中找到的最小值和最大值。
函式 minMax(struct value *root1, int num, int qStart1, int qEnd1) 獲取查詢索引並在索引範圍 qStart1 和 qEnd1 之間的陣列中查詢最小值和最大值。
檢查是否 ( qStart1 < 0 OR qEnd1 > num-1 OR qStart1 > qEnd1 )。如果為真，則查詢中的輸入範圍無效。
否則，呼叫 minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0)。
函式 minmaxFind(struct value *root, int startT, int endT, int qStart, int qEnd, int pos) 是一個遞迴函式。它獲取指向線段樹的指標 - root，當前值的起始和結束索引作為 startT 和 endT。
它還獲取查詢範圍內的起始和結束索引。線段樹中值的當前索引具有索引 pos。
如果 (qStart <= startT) 並且如果 ( qEnd >= endT)，則當前值的段是給定範圍的一部分。因此，返回該值中的最小值和最大值。
如果它在範圍之外，則使用 minVal 和 maxVal 更新當前值。
如果當前部分與給定範圍重疊，則：
獲取 middl = startT + ( endT - startT )/2。
獲取 p1 和 p2 作為 2*pos+1 和 =2*pos+2。
將 lpos 更新為 lpos = minmaxFind(root, startT, middl, qStart, qEnd, p1) 並將 rpos 更新為 minmaxFind(root, middl+1, endT, qStart, qEnd, p2)。
將 temp.minVal 設定為 lpos.minVal 和 rpos.minVal 的最小值。
將 temp.maxVal 設定為 lpos.maxVal 和 rpos.maxVal 的最大值。
返回 temp。
函式 segmentTree(int arr2[], int startT2, int endT2, struct value *root2, int pos2) 用於為陣列 arr2[] 構造一個線段樹，其中索引範圍為 startT2 和 endT2，當前值位置為 pos2。
函式 *createTree(int arr0[], int num0) 用於從給定陣列 arr0 構造線段樹。此函式為線段樹分配記憶體，並呼叫 segmentTree() 進行記憶體分配。
示例
#include<bits/stdc++.h>
using namespace std;
struct value{
int minVal;
int maxVal;
};
struct value minmaxFind(struct value *root, int startT, int endT, int qStart,
int qEnd, int pos){
struct value temp, lpos ,rpos;
if (qStart <= startT) {
if( qEnd >= endT)
{ return root[pos]; }
}
if (endT < qStart || startT > qEnd) {
temp.minVal = 9999;
temp.maxVal = -9999;
return temp;
}
int middl = startT + ( endT - startT )/2;
int p1=2*pos+1;
int p2=2*pos+2;
lpos = minmaxFind(root, startT, middl, qStart, qEnd, p1);
rpos = minmaxFind(root, middl+1, endT, qStart, qEnd, p2);
temp.minVal = (lpos.minVal<rpos.minVal) ? lpos.minVal : rpos.minVal ;
temp.maxVal = (lpos.maxVal>rpos.maxVal) ? lpos.maxVal : rpos.maxVal ;
return temp;
}
struct value minMax(struct value *root1, int num, int qStart1, int qEnd1){
struct value temp1;
if (qStart1 < 0 || qEnd1 > num-1 || qStart1 > qEnd1){
cout<<"Please enter Valid input!!";
temp1.minVal = 9999;
temp1.maxVal = -9999;
return temp1;
}
return minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0);
}
void segmentTree(int arr2[], int startT2, int endT2, struct value *root2, int pos2){
if (startT2 == endT2) {
root2[pos2].minVal = arr2[startT2];
root2[pos2].maxVal = arr2[startT2];
return ;
}
int p1=pos2*2+1;
int p2=pos2*2+2;
int middl2 = startT2+(endT2-startT2)/2;
segmentTree(arr2, startT2, middl2, root2, p1);
segmentTree(arr2, middl2+1, endT2, root2, p2);
root2[pos2].minVal = root2[p1].minVal<root2[p2].minVal ? root2[p1].minVal : root2[p2].minVal;
root2[pos2].maxVal = root2[p1].maxVal>root2[p2].maxVal ? root2[p1].maxVal : root2[p2].maxVal;
}
struct value *createTree(int arr0[], int num0) {
int height = (int)(ceil(log2(num0)));
int maxS = 2*(int)pow(2, height) - 1;
struct value *root0 = new struct value[maxS];
segmentTree(arr0, 0, num0-1, root0, 0);
return root0;
}
int main() {
int Arr[] = { 1, 2, 3, 4, 5 };
int length = sizeof(Arr)/sizeof(Arr[0]);
struct value *tree = createTree(Arr, length);
int QStart = 1;
int QEnd = 4;
struct value answer=minMax(tree, length, QStart, QEnd);
cout<<"Minimum Value : "<<answer.minVal<<endl;
cout<<"Maximum Value : "<<answer.maxVal;
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出
Minimum Value : 2 Maximum Value : 5
833 次檢視
