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 是范围内第二小的数字 [7, 8 , 1, 4 , 6 , 8 ] 表示范围从 1 到 6，6 是范围内第三小的数字
输入 − arr[] = {2, 7 , 9, 4 , 6 , 5 , 1 |
片段 1:start = 3，end = 6，k = 4
片段 2:start = 2，end = 5，k = 3
输出 − 在给定范围内小于或等于键值的数字数量为:9 7
解释 − [9, 4 , 6 , 5] 表示从 3 到 6 的范围，9 是给定范围内第四小的数字。 [7 , 9, 4 , 6 ] 表示从 2 到 4 的范围，7 是给定段范围内第三小的数字。
以下程序中使用的方法如下 −
声明一个整数类型数组。计算数组的大小。声明一个向量类型变量，构成一对整数类型。启动 FOR 循环，将数据从数组推送到向量。
对给定的向量进行排序。创建一个整数类型的向量数组，其大小为最大。
调用函数为 generateTree(1, 0, size - 1, vec, tree)，并将 getSmallestIndex 设置为 queryWrapper(2, 5, 2, size, vec, tree)。
打印输入 [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[])
检查如果 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[])
检查 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
如果 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<<"在给定范围内小于或等于键值的数字计数为:"<<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;
}
输出
如果我们运行上述代码，它将生成以下输出
在给定范围内小于或等于键值的数字计数为: 4 6
