Find K pairs with Smallest Sum

这题的线索很明显

如果[1, 7, 11] 和 [2, 4, 6] 的话,第一个无疑是从first in arrayA, first in arrayB 拿.

第二大的话有两种可能: 7,2或者 1,4.

实现起来还是很复杂的:


dis用的是一个Priority Queue的想法,跟我想的有点不一样。。。【其实是一样的,但是我没有想出来用这个data structure】

巧妙的地方在于,不是暴力的放所有combination进去再比较!

而是先把[A[i], B[0]]的所有组合放进去。n个组合。

然后pop出最小一个出来以后,放入下一个。但是这个下一个的选取很妙,是current_associated_index + 1 element in array B!  这个地方很难描述啊。。不过跟我一开始说的那个例子是一样的

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容