关于在指定区间求第k小的数，求高效率算法,该如何处理

2012-02-23

关于在指定区间求第k小的数，求高效率算法给定一个整数数列a[1..n]，其中每个元素都不相同，你的程序要能回答

关于在指定区间求第k小的数，求高效率算法
给定一个整数数列a[1..n]，其中每个元素都不相同，你的程序要能回答一组格式为Q (i , j , k)的查询，Q(i, j ,k)的意思是“在a[i..j]中第k小的数是多少？”
例如令 a = {1, 5, 2, 6, 3, 7, 4}，查询格式为Q (2 , 5 , 3)，数列段a[2..5] = {5, 2, 6, 3}，第3小的数是5，所以答案是5。

第一行包括一个正整数n，代表数列的总长度，还有一个数m，代表有m个查询。n、m满足：1≤n≤100 000，1≤m≤5 000。

第二行有n个数，代表数列的元素，所有数都不相同，而且不会超过10^9

接下来有m行，每行三个整数i、j、k，代表一次查询，i、j、k满足：1≤i≤j≤n， 1≤k≤j?i+1。

关于这个问题可能已经讨论了很多次，但是我用快排的变形还是超时，希望能看更高效的算法

[解决办法]
lz搜索一下划分树的资料吧，以前看过，不过我现在也记不太清楚了。
[解决办法]
我是这么理解的，每一次查询就是一次新的，相对于m个查询一直做是比较笨的，但我想不到高级的怎么做，所以我现在只写了一下在n个数中找第k小的数。

C/C++ code

//生成测试文件#include <fstream>#include <vector>#include <Windows.h>#include <algorithm>#include <iterator>using namespace std;void main(){    srand(GetTickCount());    vector<size_t> nums;    unsigned prenum=0;    ofstream of("testfile.txt", ios_base::out);    for (size_t i = 0 ; i < 10; ++i)    {        prenum += rand() % 3;        nums.push_back(prenum);    }    random_shuffle(nums.begin(), nums.end());    copy(nums.begin(), nums.end(), ostream_iterator<size_t>(of, " "));}
[解决办法]
划分树http://baike.baidu.com/view/4199603.htm
[解决办法]
线段树+归并排序+二分查找
[解决办法]
可以参考这个，基本上一致，表达不一样

http://blog.csdn.net/lzy18lzy/article/details/4670406
[解决办法]
上周听了北大的ACM课，讲到线段树，最关键是要离散化
离散化，很重要，凭我自己的理解，可以离散成 L= n/2个线段。
每个单位线段就是(max-min)/L这么宽。
把L个区间插入线段树，结点上存放本段的点的命中数量Count.
最终叶子节点不创建即可。
总体复杂度是O(n)


找到i,j花费Logi +logj,再根据Count很容易得到第K，每次查找都是对数级别的。
就第一次需要线性的。

http://baike.baidu.com/view/670683.htm

热点排行

软件架构设计

关于在指定区间求第k小的数，求高效率算法,该如何处理