合并两个，三个，k个排序数组的follow-up

据观察，最近有几家会在考合并排序数组时follow up会问如果输入是streams而不是数组时如何处理。

感觉若只是在刷题网上刷题的话，很少有机会实践streams的输入和输出，面试时可能应对失当，翻船翻在了简单题上。比如前两天看到有人面刀合并三个排序数组，用了无数个if，结果面试官肯定没看懂也没兴趣搞懂对还是错。

不想纸上谈兵，附上streams输入和输出的几个Python代码实现。希望对准备面试的人有所帮助。加低分隐藏是为了阻止搜索引擎。

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

游客，您好！
本帖隐藏的内容需要积分高于 50 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

在合并2个里”while cache”是不是和”while True”没什么区别？因为cache的长度一直没变

Jiayi666 发表于 2019-5-4 19:12
在合并2个里”while cache”是不是和”while True”没什么区别？因为cache的长度一直没变

观察敏锐。你说的对，该成"while True:"可读性其实更好，最初是想在一个stream到底之后把cache长度缩短，后来改了主意，但那个"while cache:"留在哪里没改。

不太熟悉python
楼主能解释下你的思路吗

淡雪初晴 发表于 2019-5-5 01:59
不太熟悉python
楼主能解释下你的思路吗

这个思路方面并没有任何新奇之处，本楼主假定看贴的人已经会熟练的写静态数组的二路归并和K路归并，发这个贴的目的是提醒大家，stream input/output 的语法不同于静态数组，一些小细节的处理也不一样。

本来Python是没学过的人也大致能看懂的，但这里用到了yield和exception，就没法解释了。

这个代码最好是和标准的静态数组解法对照着看，后者刷题网上有。路过的写JAVA的，希望能发一下stream based K路归并，我给加米噢。

非常感谢分享

关于楼上while True的观点，我有个看法，分享一下。

因为这个问题是刷题网 尔伞 的变体，而那个原题是linked list。所以我想楼主的写法while cache其实更适合原题，因为遍历linked list的时候需要把已经变空的指针丢掉不再考虑，而while True更适合stream。

nowhy 发表于 2019-5-7 19:05
关于楼上while True的观点，我有个看法，分享一下。

因为这个问题是刷题网 尔伞 的变体，而那个原题是li ...

k路归并时，因为用的是堆，这个 while cache: 是正解。

Jiayi666网友的意思是，在二路和三路归并里，那个cache是数组，不会变小一直到零，while cache: 就比较突兀，虽然功能上没有毛病。

https://github.com/python/cpython/blob/2.7/Lib/heapq.py#L357

这个就是heapq.merge吧...