给定一个由n个数字组成的数组，任务是回答以下问题：
null
kthSmallest(start, end, k) : Find the Kth smallest
number in the range from array
index 'start' to 'end'.
例如：
Input : arr[] = {3, 2, 5, 1, 8, 9|
Query 1: start = 2, end = 5, k = 2
Query 2: start = 1, end = 6, k = 4
Output : 2
5
Explanation:
[2, 5, 1, 8] represents the range from 2 to
5 and 2 is the 2nd smallest number
in the range[3, 2, 5, 1, 8, 9] represents
the range from 1 to 6 and 5 is the 4th
smallest number in the range
关键的想法是建立一个 分段树 每个节点上都有一个向量，该向量按排序顺序包含子范围的所有元素。如果我们观察这段树的结构，这和 合并排序算法 （这就是为什么它被称为合并排序树）
我们使用与中讨论的相同的实现 合并排序树（给定行范围内较小或相等的元素）
首先，我们维护一个对向量，其中每对{value，index}的第一个元素表示输入数组的元素，第二个元素表示它出现的索引。
现在我们根据每对向量的第一个元素对向量进行排序。
在此之后，我们构建了一个合并排序树，其中每个节点在排序范围内都有一个索引向量。
当我们必须回答一个问题时，我们会发现 th 最小的数字位于左子树或右子树中。其思想是使用两个二进制搜索，并在左子树中找到元素的数量，以便索引位于给定的查询范围内。 设此类指数的数量为M。
如果M>=K，这意味着我们将能够找到K th 左子树中的最小数，因此我们调用左子树。
否则K th 最小的数字位于正确的子树中，但这次我们不必寻找K th 最小数因为我们已经在左子树中找到了范围的前M个最小数，所以我们应该寻找剩余部分，即（K-M） th 右子树中的数字。
这是K的索引 th 最小值此索引处的值是所需的数字。
// CPP program to implement k-th order statistics #include <bits/stdc++.h> using namespace std; const int MAX = 1000; // Constructs a segment tree and stores tree[] void buildTree( int treeIndex, int l, int r, vector<pair< int , int > > &a, vector< int > tree[]) { /* l => start of range, r => ending of a range treeIndex => index in the Segment Tree/Merge Sort Tree */ /* leaf node */ if (l == r) { tree[treeIndex].push_back(a[l].second); return ; } int mid = (l + r) / 2; /* building left subtree */ buildTree(2 * treeIndex, l, mid, a, tree); /* building left subtree */ buildTree(2 * treeIndex + 1, mid + 1, r, a, tree); /* merging left and right child in sorted order */ merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin(), tree[2 * treeIndex + 1].end(), back_inserter(tree[treeIndex])); } // Returns the Kth smallest number in query range int queryRec( int segmentStart, int segmentEnd, int queryStart, int queryEnd, int treeIndex, int K, vector< int > tree[]) { /* segmentStart => start of a Segment, segmentEnd => ending of a Segment, queryStart => start of a query range, queryEnd => ending of a query range, treeIndex => index in the Segment Tree/Merge Sort Tree, K => kth smallest number to find */ if (segmentStart == segmentEnd) return tree[treeIndex][0]; int mid = (segmentStart + segmentEnd) / 2; // finds the last index in the segment // which is <= queryEnd int last_in_query_range = (upper_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin()); // finds the first index in the segment // which is >= queryStart 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 >= K) { // Kth smallest is in left subtree, // so recursively call left subtree for Kth // smallest number return queryRec(segmentStart, mid, queryStart, queryEnd, 2 * treeIndex, K, tree); } else { // Kth smallest is in right subtree, // so recursively call right subtree for the // (K-M)th smallest number return queryRec(mid + 1, segmentEnd, queryStart, queryEnd, 2 * treeIndex + 1, K - M, tree); } } // A wrapper over query() int query( int queryStart, int queryEnd, int K, int n, vector<pair< int , int > > &a, vector< int > tree[]) { return queryRec(0, n - 1, queryStart - 1, queryEnd - 1, 1, K, tree); } // Driver code int main() { int arr[] = { 3, 2, 5, 1, 8, 9 }; int n = sizeof (arr)/ sizeof (arr[0]); // vector of pairs of form {element, index} vector<pair< int , int > > v; for ( int i = 0; i < n; i++) { v.push_back(make_pair(arr[i], i)); } // sort the vector sort(v.begin(), v.end()); // Construct segment tree in tree[] vector< int > tree[MAX]; buildTree(1, 0, n - 1, v, tree); // Answer queries // kSmallestIndex hold the index of the kth smallest number int kSmallestIndex = query(2, 5, 2, n, v, tree); cout << arr[kSmallestIndex] << endl; kSmallestIndex = query(1, 6, 4, n, v, tree); cout << arr[kSmallestIndex] << endl; return 0; } |
输出：
2 5
因此，我们可以得到K th L到R范围内的最小数字查询，以O（n（logn）为单位 2. )通过在索引上构建合并排序树。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
