資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++ 中的歸併排序樹
給定一個整數陣列、一組區段起始和結束指標以及一個鍵值，問題陳述是找到給定範圍內小於或等於給定鍵值的所有值。
讓我們用例子來理解
輸入− arr[] = {7, 8 , 1, 4 , 6 , 8 , 10 }
區段 1：起始 = 2，結束 = 4，k = 2
區段 2：起始 = 1，結束 = 6，k = 3
輸出− 給定範圍內小於或等於鍵值的數字個數為 2 6
說明− [8, 1, 4] 表示從 2 到 4 的範圍，2 是該範圍內第 2 小的數 [7, 8 , 1, 4 , 6 , 8 ] 表示從 1 到 6 的範圍，6 是該範圍內第 3 小的數
輸入− arr[] = {2, 7 , 9, 4 , 6 , 5 , 1 }
區段 1：起始 = 3，結束 = 6，k = 4
區段 2：起始 = 2，結束 = 5，k = 3
輸出− 給定範圍內小於或等於鍵值的數字個數為：9 7
說明− [9, 4 , 6 , 5] 表示從 3 到 6 的範圍，9 是該範圍內第 4 小的數 [7 , 9, 4 , 6 ] 表示從 2 到 4 的範圍，7 是該區段範圍內第 3 小的數
下面程式中使用的方法如下：
宣告一個整數型別陣列。計算陣列的大小。宣告一個向量型別變數，形成整數型別的對。啟動 FOR 迴圈以將資料從陣列推送到向量。
對給定的向量進行排序。建立一個具有最大大小的整數型別向量陣列。
呼叫函式 generateTree(1, 0, size - 1, vec, tree) 並將 getSmallestIndex 設定為 queryWrapper(2, 5, 2, size, vec, tree)。
列印 input[getSmallestIndex]。
將 getSmallestIndex 設定為呼叫函式 queryWrapper(1, 6, 4, size, vec, tree)。
在函式 void generateTree(int treeIndex, int leftIndex, int rightIndex, vector<pair<int, int> > &a, vector<int> tree[]) 內部
檢查 IF leftIndex 到 rightIndex 然後設定 tree[treeIndex].push_back(a[leftIndex].second) 並返回
將 midValue 設定為 (leftIndex + rightIndex) / 2 並呼叫 generateTree(2 * treeIndex, leftIndex, midValue, a, tree), generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree) 和 merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin(), tree[2 * treeIndex + 1].end(),back_inserter(tree[treeIndex]))
在函式 int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector tree[]) 內部
檢查 IF startIndex 到 endIndex 然後返回 tree[treeIndex][0]
將 mid 設定為 (startIndex + endIndex) / 2，last_in_query_range 設定為 (upper_bound(tree[2 * treeIndex].begin(),tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin())
將 first_in_query_range 設定為 (lower_bound(tree[2 * treeIndex].begin(),tree[2 * treeIndex].end(), queryStart) - tree[2 * treeIndex].begin()) 並將 M 設定為 last_in_query_range - first_in_query_range
檢查 IF M 大於等於 key 然後返回 calculateKSmallest(startIndex, mid, queryStart,queryEnd, 2 * treeIndex, key, tree)
否則，返回 calculateKSmallest(mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, key - M, tree)。
在函式 int queryWrapper(int queryStart, int queryEnd, int key, int n, vector<pair<int, int> > &a, vector<int>tree[]) 內部
返回對函式 calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree) 的呼叫
示例
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
void generateTree(int treeIndex, int leftIndex, int rightIndex, vector<pair<int, int> > &a, vector<int> tree[]){
if (leftIndex == rightIndex){
tree[treeIndex].push_back(a[leftIndex].second);
return;
}
int midValue = (leftIndex + rightIndex) / 2;
generateTree(2 * treeIndex, leftIndex, midValue, a, tree);
generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree);
merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin(),
tree[2 * treeIndex + 1].end(), back_inserter(tree[treeIndex]));
}
int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector<int> tree[]){
if (startIndex == endIndex){
return tree[treeIndex][0];
}
int mid = (startIndex + endIndex) / 2;
int last_in_query_range = (upper_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin());
int first_in_query_range = (lower_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(),queryStart) - tree[2 * treeIndex].begin());
int M = last_in_query_range - first_in_query_range;
if (M >= key){
return calculateKSmallest(startIndex, mid, queryStart, queryEnd, 2 * treeIndex, key, tree);
}
else {
return calculateKSmallest(mid + 1, endIndex, queryStart,queryEnd, 2 * treeIndex + 1, key - M, tree);
}
}
int queryWrapper(int queryStart, int queryEnd, int key, int n,
vector<pair<int, int> > &a, vector<int> tree[]){
return calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree);
}
int main(){
int input[] = { 7, 8 , 1, 4 , 6 , 8 , 10 };
int size = sizeof(input)/sizeof(input[0]);
vector<pair<int, int> > vec;
for (int i = 0; i < size; i++) {
vec.push_back(make_pair(input[i], i));
}
sort(vec.begin(), vec.end());
vector<int> tree[MAX];
generateTree(1, 0, size - 1, vec, tree);
cout<<"Count of number which are smaller than or equal to key value in the given range are:"<<endl;
int getSmallestIndex = queryWrapper(2, 4, 2, size, vec, tree);
cout << input[getSmallestIndex] << endl;
getSmallestIndex = queryWrapper(1, 6, 3, size, vec, tree);
cout << input[getSmallestIndex] << endl;
return 0;
}輸出
如果我們執行上述程式碼，它將生成以下輸出
Count of number which are smaller than or equal to key value in the given range are: 4 6
543 次瀏覽
