题目描述：给定一个数组，需要多次查找不同区间内的，第k大或者第k小的元素。
考虑题目是多次查找，如果采用只对查询区间内的元素进行排序的思路，然后输出第k大的数的策略，那么下一次进行查询时，还需要对另外一个区间进行排序，再次查找。而且，如果两次查询的区间有重叠区域的话，第一次排序时已经破坏了数组，使得第二次查询无法进行。
针对这种问题，思路之一是采用伴随数组的方法：首先，定义一个结构体，一个是数组元素，另一个是数组原来的标号，记录每个数在数组的原顺序。例子如下：
原数组如下，第一次需要查询区间[2, 5]中第3小的数（假设数组下标以1开头）：
a[i].data 1 5 2 6 3 7 4
a[i].num 1 2 3 4 5 6 7
可以对整个数组进行排序，然后得到的序列应该是（注：原下标始终保持不变）：
a [i].data 1 2 3 4 5 6 7
a [i].num 1 3 5 7 2 4 6
如上，既然数据现在已经从小到大排好了，那么，我们只需要进行一次检索，从最小的数到最大的数，我们找第k(k=3)小的数，当我们发现下标a[i].num在区间[2,5]中的时候，k--，那么当k==0的时候，我们也就找到了原区间内第k(3)小的数了。如下：
a [i].data 1 2 3 4 5 6 7
a [i].num 1 3 5 7 2 4 6
k 3 2 1 1 0
所以，在原区间[2,5]中，第k（3）小的数是5。
代码如下：
struct node{
int num,data;
bool operator < (const node &p) const
{
return data < p.data;
}
};
node p[100001];
int main()
{
int n,m,i,j,a,b,c;
printf("inputthe set len and search times:");
while(scanf("%d %d",&n,&m)!=EOF)
{
printf("input %d numbers ", n);
for(i=1;i<=n;i++)
{
scanf("%d",&p[i].data);
p[i].num = i;
}
sort(p+1,p+1+n);
for(j=1;j<=m;j++)
{
printf("input the interval and thekth: ");
scanf("%d %d %d",&a,&b,&c);
printf("the %d smallest num is: ", c);
for(i=1;i<=n;i++)
{
if(p[i].num>=a && p[i].num<=b)
c--;
if(c == 0)
break;
}
printf("%d ",p[i].data);
}
}
return0;
}
该算法的时间复杂度，排序数组需要O(n*lgn)的时间，查找m次，需要O(mn)的时间，所以，总的时间复杂度为O(n*lgn + mn)。
http://blog.csdn.net/v_JULY_v/article/details/6452100