@Strikeactor
@guchengf
是，然而同样使用多说新版主页却没有弹出啊，是不是我新版主页的代码有问题吗？

@wangfeijs 哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈。。。。。。我只是觉得很奇怪啊为什么会这样调用方法哪里有问题，太奇怪了。。。

@yaqink 啊v站逛得比较少（。）＿（：з」∠）＿

@Kilerd 哦

@Septembers 功利一点，如果只为工作服务呢

@slayer 29题不是和30差不多嘛，top k

@binux 当时没想到嘛！！！！看到下面的回复就会了！！！！＿（：з」∠）＿
@yyai3 综合你们两个的！！！我找到思路了！！！！


先写个伪代码，大家看看对不对




对K排序

void batch_select(int A[],int K[],int A_low,int A_high,int k_low,int k_high){
if (k_high-k_low)<1{
result[k_low]=select(A,A_low,A_high,K[k_low]);//result数组用来存放结果
return;
}
else if (k_high-k_low)==1 {
result[k_low]=select(A,A_low,A_high,K[k_low]);
result[k_high]=select(A,A_low,A_high,K[k_high]);
return;
}
else {
在S中找到select(A,A_low,A_high,K[(k_low+k_high)/2]),分成两组，返回此数字的元素位置为A_mid
for (int i=(k_low+k_high)/2;i<=k_high;i++){
K[i]=K[i]-A_mid;

}
result[(k_low+k_high)/2]=S[A_mid];
batch_select(A,K,A_low,A_mid-1,k_low,(k_low+k_high)/2);
batch_select(A,K,A_mid+1,A_high,(k_low+k_high)/2,k_high);
return;

}


}

@Angdo 应该就是上面这个思路吧，其实和yyai3的一个意思，他就是没说的很明白

@dingyaguang117 如果是有序的，那找第k小元素的时间复杂度是O(1)哦

@hpeng 谢谢谢谢！！！！！原来是这个！！！！

@sumhat @jiang42 原图已经旋转了，抱歉带来不方便了

@binux 感谢层主

小的那一部分没有问题，大的一部分的k就不是之前的k了呀，大的一部分的第k小元素，就不是S里的第K小元素了呀

顺着层主的思路想了一下，如果按照这样递归，就变成了快速排序了啊

@dingyaguang117 S不是有序集合，S是无序集合，SELECT的功能就是在无序集合中找到k小元素，时间复杂度为O(n)
如果是这样的话，那直接二分搜索了啊。。。。

真不错，重度google患者感谢楼主！

chrome 40 1366*768