二流学校自学算法，在做练习题的时候这道题不会（6.30）
http://ww4.sinaimg.cn/large/6b8bbe7ejw1eqyep46iiaj21ts35sb2a.jpg
http://ww3.sinaimg.cn/large/6b8bbe7ejw1eqyet817qyj21ts35s4qq.jpg
你们敢相信我这算法老师也不懂？？？我感觉他连题目都没看懂。。。。。他以为是一个进去找一个出来。。。那SELECT算法时间复杂度已经是O(n)了，还需要啥O(n logr)...
谷歌了也没找到。。。。。。。
 |
1
dingyaguang117 Apr 8, 2015 via iPhone
看描述S是有序集合。
题目应该是让你这样做，S中找出ki小 => S分成2段，前一段找到ki小，其中ki要小于S长度的一半，后一段也是一样。 应该是这样的分治吧 |
 |
2
xingo OP @dingyaguang117 S不是有序集合，S是无序集合，SELECT的功能就是在无序集合中找到k小元素，时间复杂度为O(n)
如果是这样的话，那直接二分搜索了啊。。。。 |
 |
3
binux Apr 8, 2015
什么叫『第 k 个最小元素』？『最』了怎么还有『第』？
|
|
4
binux Apr 8, 2015  1
我假设就是第 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 |
 |
5
sumhat Apr 8, 2015
发图之前请先转一下角度 -_-
|
 |
6
jiang42 Apr 9, 2015
发图醉了。。。。
|
 |
7
Andiry Apr 9, 2015
这图喷了，@binux 是正解。先找中位数，然后分治
|
|
8
xingo OP |
 |
10
yyai3 Apr 9, 2015 1
@xingo 使用二分查找，先取出S中某个数，将S分割成两半（S1，S2），S1集合的总数为n1，
K中小于n1的数，继续在S1集合中找，直到K集合为空 K中大于n1的数，在S2集合中找，查找的位置为K-n1，直到K集合为空 K中等于n1+1的数，则返回。并从集合K中删除 |
|
12
dingyaguang117 Apr 9, 2015
@xingo 如果不是有序，平凡的消耗O（r*n）这句话就有问题了，O（N）能选择出一个无序数组中的第x小元素？
|
 |
13
Angdo Apr 9, 2015 via iPhone
select 查找第k小元素本来就是 O n的 for循环 1到r使算法变成nr 把1-r那块变成 logr 不就是nlogr的了？
|
|
15
Angdo Apr 9, 2015 via iPhone
@dingyaguang117 'SELECT算法就是用来查找第k小元素的算法 为O n 题目意思是查找第k1到kr小元素就直接for循环从k1计算到kr 为O r 一共就是O nr
|
|
16
Angdo Apr 9, 2015 via iPhone 1
之前错了先把k排序O rlogr 再取中值 select 得到 第k r/2 小元素 这时 S被分成了两部分 前面小于 第k r/2 小元素 后面大于第k r/2 小元素 然后两部分k再取中值 重复上面
|
 |
17
hpeng Apr 9, 2015 via Android
如果你想不明白那个正解，给个关键字你搜 top k
|
|
18
xingo OP @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 谢谢谢谢！！！！！原来是这个！！！！ |
|
19
Angdo Apr 9, 2015 via iPhone
@xingo 在select最后已经把s分成两部分在select里递归select书上那什么比k小数组a什么和select 比k大，直接修改select算法
|
|
20
Angdo Apr 9, 2015 via iPhone
@xingo k先排序 把select改成输入数组k 分成比k小的数组 和比k大的数组 然后再select里取中值 按原来select一遍 select最后会把s分成两份 然后两部分递归select
|
 |
23
slayer Apr 10, 2015
这题大概懂了，但是29题是怎么回事？SELECT选出了第k小元素X，那么前面的不都是比X还小的元素，直接都返回就可以了吧，还是O(n)都复杂度。
|
Select Language