推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 636|回复: 16
收起左侧

[算法题] m个有序数组求第k小的数字

[复制链接] |试试Instant~ |关注本帖
magicsets 发表于 2017-6-24 13:50:59 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
本帖最后由 magicsets 于 2017-6-24 20:56 编辑

最近遇到了这个问题,觉得挺有意思所以分享一下。不过不是面试遇到的.. 感觉这题目不知道解法的话短时间内完全做不出来(可以拿来面试时为难别人...)。

题目很简单,就是说有m个数组,长度不一定相等,总共合起来有N个元素,每个数组里的数字按从小到大已经排好序。给定k,要求在m * log(N)的时间内找到这所有N个数字中第k小的数字。

(这个问题的简单版本是一个LeetCode上的面试题:在m=2个有序数组中找中位数或者第k小的数字。不限制m之后就难了很多。)


----
注:m比较小而N很大,k可以任意取值,参考值m = 100,N = 10^9,k = N / 3。

滚动的西瓜 发表于 2017-6-25 00:30:19 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
FightForTomo 发表于 2017-6-24 22:35
错,我这个是KlogM。

O()时间复杂度和非定量K肯定不能有关系的。现在所谓的时间复杂度,都是算的是最大时间复杂度规模O()。

——————————
wiki:
在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。 这是一个代表算法输入值的字符串的长度的函数。 ... 例如,如果一个算法对于任何大小为n (必須比n0 大)的输入,它至多需要5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是O(n3)。
回复 支持 1 反对 0

使用道具 举报

 楼主| magicsets 发表于 2017-6-27 11:31:17 | 显示全部楼层
关注一亩三分地微博:
Warald
本帖最后由 magicsets 于 2017-6-27 11:59 编辑

这里贴一下问题的答案吧

这确实是一道比较难的题目,算法步骤略长,详细的解释与时间复杂度分析在这篇论文里:

Peter J. Varman, Scott D. Scheufler, Balakrishna R. Iyer, and Gary R. Ricard. 1991. Merging multiple lists on hierarchical-memory multiprocessors. J. Parallel Distrib. Comput. 12, 2 (June 1991)
https://github.com/jqdocshare/do ... tiseq_partition.pdf

文章里解决的是稍微更general一点的问题:将每个有序数组都partition为左右两边,使得所有的左边合起来正好是前k小的数字。里面的细节我就不翻写一遍了,因为很麻烦.. 得贴图才能解释清楚,不过如果有难以理解的地方我可以跟帖。

此外上述的partition版本是一个有实际用途的算法,它是并行多路归并排序算法(Parallel Multiway Mergesort)中重要的一步。
我遇到这个问题是因为想找一个单机多核排序的实现(C++,无GPU,workload是10亿量级的64位整数),然后发现gcc的并行多路归并排序是最有效使用多CPU(4核 ~ 20核)并且是最快的。此外gcc和tbb都有Parallel Balanced Quicksort,然而相对较慢。

这里是gcc的libstdc++中对该题算法的实现:https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/parallel/multiseq_selection.h#L388
用了260行代码

PS:
关于如何使用gcc的并行库:https://stackoverflow.com/questions/28520720/c-parallel-sort
我猜大多数人都没用过.. 但是如果你手上的电脑有4核或者8核,然后原来处理某些数据要等个10分钟,用下并行说不定就两三分钟了,还是很爽的。



回复 支持 1 反对 0

使用道具 举报

moonyellow 发表于 2017-6-24 14:11:25 | 显示全部楼层
感觉确实有点难度啊。。。。。
回复 支持 反对

使用道具 举报

滚动的西瓜 发表于 2017-6-24 17:24:02 | 显示全部楼层
思路可以从二分入手,细节还没想好
回复 支持 反对

使用道具 举报

FightForTomo 发表于 2017-6-24 20:18:14 | 显示全部楼层
本帖最后由 FightForTomo 于 2017-6-24 20:22 编辑

整个小堆,都塞堆里。NlogN

哦 MlogN啊。

那按照每个数组的第一个元素放到堆里。然后出堆堆时候就把出堆堆数组第一个数给删除了。再放回去。这样就MlogN了。

二分搜索咋搜?
回复 支持 反对

使用道具 举报

滚动的西瓜 发表于 2017-6-24 20:58:23 | 显示全部楼层
FightForTomo 发表于 2017-6-24 20:18
整个小堆,都塞堆里。NlogN

哦 MlogN啊。

你这个不是NlogM吗
回复 支持 反对

使用道具 举报

FightForTomo 发表于 2017-6-24 22:35:19 | 显示全部楼层

错,我这个是KlogM。
回复 支持 反对

使用道具 举报

ewyu 发表于 2017-6-25 00:03:56 | 显示全部楼层
建一个最小堆,用堆排序
回复 支持 反对

使用道具 举报

33847682 发表于 2017-6-25 00:12:34 | 显示全部楼层
感觉思路是不是有点儿像median of medians?
回复 支持 反对

使用道具 举报

newgod2500 发表于 2017-6-25 00:49:09 | 显示全部楼层
本帖最后由 newgod2500 于 2017-6-25 02:19 编辑

比较暴力,General(如果数组无序)一点的思路是建一个minHeap, 把N个元素塞进去,然后按k取值,这样时间复杂度是O(N+k),空间要求是O(N); 不太符合题意  (当然把N个元素重新sort,就更暴力了)

既然我们知道了M, N和K的话, N是个很大的数字,意味着N/M 也是个大数,我们的思路最好不要跟N挂上钩。

每个数组都是有序的(假设是升序,降序的话方向需要反过来;无论如何变化都是从M个数组里,每个数组的最小数开始),我们改进一下思路。
首先建一个priority queue, 然后把M个数组的第一个元素Enqueue进去。大概思路跟LeetCode 上 378很像。不过378的输入是个matrix, 这里是个 jagged array-like的输入。
然后根据k来写一个while循环,做k次操作,每次只对priority queue的头一个元素, 头元素是largest element in the pq进行操作,下面的代码可能有Bug,我没检查,但大概思路是正确的:

while(K > 0)
{
    start = pq.First();
    int x = pq.First().Item1;   // index among in the M arrays
    int y = pq.First().Item2;   // index in the M[x] array
    pq.RemoveAt(0);             //Remove the first

    if(y < M[x].Length - 1)
    {
       pq.Insert(M[x][y+1]);
     }
     k--;
}
return start;

因为C#里没有pq, 只有SortedDictionary 和SortedList, 如果K很大的话(此处是N/3,优先考虑SortedDicitonary来满足最快的插入和删除performance =>都是O(logN))

时间复杂度是O(M*logK + k) , 空间上因为我们一直维持着一个size 为M 的优先队列,可以认为是O(M)
在大部分情况下, 是比O(M*logN)是要快一点的。不知道我的方法是否符合要求。
Updated:
经朋友提醒,时间复杂度应该是
M个数组第一项建堆 是O(M*logM), 然后取k次最小值是 K*logM 所以总的应该是 O(K*logM), 考虑到k可能会很大 所以应该是趋近于O(N*logM)





回复 支持 反对

使用道具 举报

youziwry 发表于 2017-6-25 01:56:56 | 显示全部楼层
newgod2500 发表于 2017-6-25 00:49
比较暴力,General(如果数组无序)一点的思路是建一个minHeap, 把N个元素塞进去,然后按k取值,这样时间复杂 ...

你这个时间复杂度不对吧 M个数组第一项建堆 是O(M*logM), 然后取k次最小值是 K*logM 所以总的应该是 O(K*logM), 考虑到k可能会很大 所以应该是趋近于O(N*logM)
回复 支持 反对

使用道具 举报

newgod2500 发表于 2017-6-25 02:18:41 | 显示全部楼层
youziwry 发表于 2017-6-25 01:56
你这个时间复杂度不对吧 M个数组第一项建堆 是O(M*logM), 然后取k次最小值是 K*logM 所以总的应该是 O(K* ...

第一项建堆的时候分析遗漏了哈哈。 你分析是对的。
回复 支持 反对

使用道具 举报

beetle 发表于 2017-6-25 02:28:42 | 显示全部楼层
随机选取一个数,每个数组用binary search找出小于这个数的index, 这样就把所有数分成两部分,a和n-a,再对比a和k决定丢掉哪一半。通过选取最长array的中位数能够避免worst case
回复 支持 反对

使用道具 举报

leonardcohen 发表于 2017-6-25 02:32:12 | 显示全部楼层
Merge K sorted List ?
Time : n Log k
Space O(k)
回复 支持 反对

使用道具 举报

newgod2500 发表于 2017-6-25 02:48:02 | 显示全部楼层
leonardcohen 发表于 2017-6-25 02:32
Merge K sorted List ?
Time : n Log k
Space O(k)

Space怎么会是O(k)?
回复 支持 反对

使用道具 举报

frozencookie 发表于 2017-6-26 14:15:21 | 显示全部楼层
从(min+max)/2开始二分,直到所有数组左边的数的个数等于K。从所有数组找到的分界点中,选取最大的那个,就可以了。复杂度m*log(n)。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-25 01:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表