一道分治算法问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3507 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

第 1 条附言 · 2015-04-09 07:32:56 +08:00

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

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

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

分治

练习题

二流

24 条回复 • 2015-04-10 06:50:43 +08:00

dingyaguang117

2015-04-08 22:15:55 +08:00 via iPhone

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

xingo

2015-04-08 22:26:00 +08:00

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

binux

2015-04-08 22:26:18 +08:00

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

binux

2015-04-08 23:12:49 +08:00

我假设就是第 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

2015-04-08 23:18:20 +08:00

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

jiang42

2015-04-09 00:10:39 +08:00

发图醉了。。。。

Andiry

2015-04-09 01:07:55 +08:00

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

xingo

2015-04-09 07:25:16 +08:00

@binux 感谢层主

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

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

xingo

2015-04-09 07:33:43 +08:00

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

yyai3

2015-04-09 09:31:58 +08:00

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

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

binux

2015-04-09 09:50:48 +08:00

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

dingyaguang117

2015-04-09 10:25:41 +08:00

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

Angdo

2015-04-09 10:29:11 +08:00 via iPhone

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

Angdo

2015-04-09 10:41:01 +08:00 via iPhone

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

Angdo

2015-04-09 10:51:20 +08:00 via iPhone

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

Angdo

2015-04-09 11:07:30 +08:00 via iPhone

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

hpeng

2015-04-09 12:45:19 +08:00 via Android

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

xingo

2015-04-09 13:41:43 +08:00

@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

2015-04-09 18:55:28 +08:00 via iPhone

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

Angdo

2015-04-09 19:05:03 +08:00 via iPhone

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

Angdo

2015-04-09 19:07:23 +08:00 via iPhone

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

lvfujun

2015-04-09 21:08:10 +08:00

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

slayer

2015-04-10 06:46:13 +08:00

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

xingo

2015-04-10 06:50:43 +08:00 via Android

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