一道分治算法问题

[xingo]

二流学校自学算法，在做练习题的时候这道题不会（6.30）
http://ww4.sinaimg.cn/large/6b8bbe7ejw1eqyep46iiaj21ts35sb2a.jpg
http://ww3.sinaimg.cn/large/6b8bbe7ejw1eqyet817qyj21ts35s4qq.jpg

你们敢相信我这算法老师也不懂？？？我感觉他连题目都没看懂。。。。。他以为是一个进去找一个出来。。。那SELECT算法时间复杂度已经是O(n)了，还需要啥O(n logr)...
谷歌了也没找到。。。。。。。

原图旋转了，大家看这里-。-
http://img.itc.cn/photo/ofeQN8w3KEp
http://img.itc.cn/photo/ofeQh2U7Atp

第k最小元素的意思就是如数列1　2　3　4　5　6　7　8　9
2就是这个数列的第2最小元素

书是算法设计技巧与分析　沙特版的

[dingyaguang117]

看描述S是有序集合。
题目应该是让你这样做，S中找出ki小
=>
S分成2段，前一段找到ki小，其中ki要小于S长度的一半，后一段也是一样。
应该是这样的分治吧

[xingo]

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

[binux]

什么叫『第 k 个最小元素』？『最』了怎么还有『第』？

[binux]

我假设就是第 k 小的元素好了

首先把 K 排序，取第 r/2 个元素，SELECT 从 S 中找到第 K(r/2) 小元素 S(r/2)。
将 S 按照 S(r/2) 分割为两半，一半全小于 S(r/2) 一半全大于 S(r/2)。
在小的那一半中查找 K(j<r/2)，在大的那一半查找 K(j>r/2)。
over

[sumhat]

发图之前请先转一下角度 -_-

[jiang42]

发图醉了。。。。

[Andiry]

这图喷了，@binux 是正解。先找中位数，然后分治

[xingo]

@binux 感谢层主

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

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

[xingo]

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

[yyai3]

@xingo 使用二分查找，先取出S中某个数，将S分割成两半（S1，S2），S1集合的总数为n1，

K中小于n1的数，继续在S1集合中找，直到K集合为空
K中大于n1的数，在S2集合中找，查找的位置为K-n1，直到K集合为空
K中等于n1+1的数，则返回。并从集合K中删除

[binux]

@xingo 你不会把大的那一半减去 K(r/2) 吗。。。

[dingyaguang117]

@xingo 如果不是有序，平凡的消耗O（r*n）这句话就有问题了，O（N）能选择出一个无序数组中的第x小元素？

[Angdo]

select 查找第k小元素本来就是 O n的 for循环 1到r使算法变成nr 把1-r那块变成 logr 不就是nlogr的了？

[Angdo]

@yyai3 这不是二分搜索 最坏情况它的时间复杂度是 On^2 每次都是最大值 导致每次都不被拆分成两部分

[Angdo]

@dingyaguang117 'SELECT算法就是用来查找第k小元素的算法 为O n 题目意思是查找第k1到kr小元素就直接for循环从k1计算到kr 为O r 一共就是O nr

[Angdo]

之前错了先把k排序O rlogr 再取中值 select 得到 第k r/2 小元素 这时 S被分成了两部分 前面小于 第k r/2 小元素 后面大于第k r/2 小元素 然后两部分k再取中值 重复上面

[hpeng]

如果你想不明白那个正解，给个关键字你搜 top k

[xingo]

@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 谢谢谢谢！！！！！原来是这个！！！！

[Angdo]

@xingo 在select最后已经把s分成两部分在select里递归select书上那什么比k小数组a什么和select 比k大，直接修改select算法

[Angdo]

@xingo k先排序 把select改成输入数组k 分成比k小的数组 和比k大的数组 然后再select里取中值 按原来select一遍 select最后会把s分成两份 然后两部分递归select

[Angdo]

@xingo 前面不小心顺序错了，select里取k中值，拆分数组k

[lvfujun]

@xingo 楼猪真是用心良苦啊.为了让广大屌丝程序猿们活动下脖子......建议第二张图再顺时针旋转180度.

[slayer]

这题大概懂了，但是29题是怎么回事？SELECT选出了第k小元素X，那么前面的不都是比X还小的元素，直接都返回就可以了吧，还是O(n)都复杂度。

[xingo]

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