| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1239 人关注过本帖
标题:子段第k小数
取消只看楼主 加入收藏
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
结帖率:50%
收藏
 问题点数:0 回复次数:0 
子段第k小数
给定一个长度为n的序列a(1),a(2),...,a(n),需要接受大量的(m个)查询(b,e,k)
查询连续子序列a(b),...,a(e)的第k小数
例如
n=5,m=1
序列2 3 1 4 5
查询3 4 2
结果为 4

输入样例
5 3
2 3 1 4 5
3 4 2
1 5 3
2 2 1

输出样例
4
3
3

因为查询数比较大
有什么好方法,可以将单次查询的复杂度降到O(n)以下,或者将整体的查询复杂度降到O(mn)以下吗?
搜索更多相关主题的帖子: 小数 序列 查询 长度 给定 
2008-01-18 17:57
快速回复:子段第k小数
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.040884 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved