FB一面，还是热乎的

水逼一枚 · 2015-10-25 11:10:43

smallshrimp 发表于 2015-10-25 07:50
如果要时间最优，应该用heap吧，参看external sort

时间最优用楼主说的binary merge和用heap都是一样的，假设K个数组，平均每个数组长度为m, 时间复杂度都为O( m * K * logK)

snowwolf · 2015-10-25 12:53:01

水逼一枚发表于 2015-10-25 10:50
请教楼主几个问题，谢谢。
1. K sorted array作为参数给你传进来的时候，是用ArrayList的方式表示的，还是 ...

不用一个一个合并吧，每次遍历所有Array的头，拿走最小的那个就是了。

水逼一枚 · 2015-10-25 13:08:26

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

幸福的小小杏儿 · 2015-10-25 13:15:10

水逼一枚发表于 2015-10-25 13:08
恩，我只是在问楼主他说的brute force是什么方法，你说的这个方法拿最小就是用heap做没错吧？只不过这题 ...

就把它们都变成linkedlist再做。。。。。

snowwolf · 2015-10-25 14:03:12

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

gamespeed · 2015-10-26 00:40:07

水逼一枚发表于 2015-10-25 10:50
请教楼主几个问题，谢谢。
1. K sorted array作为参数给你传进来的时候，是用ArrayList的方式表示的，还是 ...

不一定是java吧，取决于你用的什么语言，有可能面试官会让你自己来定

xuchen1m3fd · 2015-10-26 12:41:42

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

xuchen1m3fd · 2015-10-26 12:42:20

snowwolf 发表于 2015-10-25 12:53
不用一个一个合并吧，每次遍历所有Array的头，拿走最小的那个就是了。

这样的话时间是O(K^2*L)，复杂度很高，我也提到了这么但是最后写的不是这个

xuchen1m3fd · 2015-10-26 12:43:16

幸福的小小杏儿发表于 2015-10-25 13:15
就把它们都变成linkedlist再做。。。。。

我并不觉得面试官想让我们把这题变成链表，因为两者没有区别，如果你这么做很容易引起怀疑吧？

xuchen1m3fd · 2015-10-26 12:47:05

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式