数据结构
网络
关系数据库管理系统 (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 次浏览
