求第K小/大数这个题目经常出现，面试，考试以及OJ上都有类似的题目。
首先声明一点，个人觉得既然是第K小（大是一样的），那么重复的元素就不应该算了，当然如果算了就相对简单一些。。
最原始的解法，快排，然后取第K个数。或者是构建一个小顶堆，遍历数组取最小的K个数，再然后还有所谓的快速选择，有人证明了可以在O（n）时间内解决，不过我不太清楚这种算法是否对重复元素有效（但看了代码其实就是快排的一种应用，但个人觉得不适应于重复元素）
其实最简单的办法：
#include<algorithm>
sort(array,array+n);
unique(array,array+n)
直接调用库函数排序，去重，一般的数据这样就足够快了。
但是学了树状数组，总是看人家的代码感觉没学到什么，刚好前几日曙光也问过我同样的问题，YY了一阵子，正好用树状数组解决一下，别忘了，我们的树状数组最基本的功能哦【第i位置上村的是比左边大的数】
好了回归正题。第K小（如果是大的话就是第length-K-1小）
建树的过程必须特别注意，我们之前关于树状数组的题目中tree中每个元素都是有实际值得，但是这里我们考虑的话，某些位置是空的，也就是tree的最终大小由我们所要处理的数组中最大元素的大小决定的，所以如果使用树状数组的话，前提就是所要处理的数组中最大值不能太大【基数排序中的要求也是类似】否则内存吃不消。
在这个分类总的第一篇文章是翻译了一篇老外讲的BIT，很详细，其中有两个部分：readSingle函数和find函数当时看懂了，但是不知道实际应用在哪了，终于找到它的实际应用地方了【嘿嘿，好开心】。
建树的时候我们不能像之前那样每扫描一次数组就更新一次，因为有重复元素，一旦更新重复元素的话，树就建错了，我们就得不到所要的结果，那么怎么处理呢，这时翻译的那篇文章中提到的readSingle函数大显神威：
建树代码如下：具体的已经写在了注释中
for(int i=0;i<len;i++)
{
if((data[i]&1)==1)
{//对于基数来说，这个位置上有值就意味着有这个元素
if(!tree[data[i]])
{//当没有时才允许更新数组
update(data[i],1);
flag[data[i]]=1;
}
}
else
{/*对于偶数位置来说，以为偶数位置存储的都是一段和，不能仅仅通过当前的
值来判断，这时需要还原出原始的tree[i]了，还原就是readSingle函数，
如果还原出的值为0，就意味着这个值没有，那么我们需要更新，如果有的话，那么
就跳过更新的过程，进行下一个元素的考察*/
int tmp=readSingle(data[i]);
if(!tmp)
{
update(data[i],1);
flag[data[i]]=1;
}
}
}
树建好了，工作就完成了一大半了：
现在说一下查询第K小的数了，轮到find函数大显神威了，关于这个函数就不多做解释了，不理解的可以回去看下我之前翻译的那篇关于BIT的详细解释，跟着注释以及图就可以看明白：【唯一要说的是原版的文章中给了2种find方法，第一种是找到一个就返回，第二种就是找到最大的idx返回，但是我测试的时候发现找到一个返回就可行，但是找到最大的有问题】
//查询第K小的数
int Find_Kth(int K)
{
int idx = 0;
int bitMask=MaxVal;
int num=0;
while(bitMask)
{
num++;
bitMask>>=1;
}
bitMask=1<<(num-1);
while ((bitMask != 0) && (idx < MaxVal))
{
int tIdx = idx + bitMask;
if (K == tree[tIdx]) //找到一个就返回
return tIdx;
if (K >tree[tIdx]){
idx = tIdx;
K -= tree[tIdx];
}
bitMask >>= 1;
}
if (K != 0)
return -1;
else
return idx;
//return 1;
}
好了完整的代码如下：我们的时间复杂度为O(nlog(MaxVal))【说明一下，readSingle函数的时间复杂度为c*log(idx)，基本可以看做是常量，find_kth函数时间复杂度为O(logMaxVal)，所以总的时间复杂度为O(nlog(MaxVal))】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110000;
int n,val[N],a[N];
int len,tree[N];
bool flag[N];
int MaxVal;
int lowbit(int x){
return x&(-x);
}
void update(int x,int val){
while(x<=MaxVal){
tree[x]+=val;
x+=lowbit(x);
}
}
int getsum(int x){
int res=0;
while(x){
res+=tree[x];
x-=lowbit(x);
}
return res;
}
int readSingle(int idx)
{
int sum = tree[idx]; // sum will be decreased
if (idx > 0)
{ // special case
int z = idx - (idx & -idx); // make z first
idx--; // idx is no important any more, so instead y, you can use idx
while (idx != z)
{ // at some iteration idx (y) will become z
sum -= tree[idx];
// substruct tree frequency which is between y and "the same path"
idx -= (idx & -idx);
}
}
return sum;
}
//查询第K小的数
int Find_Kth(int K)
{
int idx = 0;
int bitMask=MaxVal;
int num=0;
while(bitMask)
{
num++;
bitMask>>=1;
}
bitMask=1<<(num-1);
while ((bitMask != 0) && (idx < MaxVal))
{
int tIdx = idx + bitMask;
if (K == tree[tIdx])
return tIdx;
if (K >tree[tIdx]){
idx = tIdx;
K -= tree[tIdx];
}
bitMask >>= 1;
}
if (K != 0)
return -1;
else
return idx;
//return 1;
}
int main(){
//不考虑重复的数
int data[10]={1,2,2,2,2,2,2,3,10,5};
MaxVal=10;
len=10;
//update(1,1);
/*扫描数组，对于位置为奇数和偶数分开处理
flag数组记录有哪些元素，因为我们最终找到的值是一个和，仍然需要进行下一步处理
即向前搜索找到一个存在的值，那么如果再用readSingle函数太麻烦，用一次之后就用
flag标记一下就可以下次用了*/
for(int i=0;i<len;i++)
{
if((data[i]&1)==1)
{//对于基数来说，这个位置上有值就意味着有这个元素
if(!tree[data[i]])
{//当没有时才允许更新数组
update(data[i],1);
flag[data[i]]=1;
}
}
else
{/*对于偶数位置来说，以为偶数位置存储的都是一段和，不能仅仅通过当前的
值来判断，这时需要还原出原始的tree[i]了，还原就是readSingle函数，
如果还原出的值为0，就意味着这个值没有，那么我们需要更新，如果有的话，那么
就跳过更新的过程，进行下一个元素的考察*/
int tmp=readSingle(data[i]);
if(!tmp)
{
update(data[i],1);
flag[data[i]]=1;
}
}
}
//我们取得了第4小的值，但是这个位置到底有没有值，需要通过flag数组来判断
int res=Find_Kth(4);
while(!flag[res])
res--;
printf("%d",res);
return 0;
}