g家店面面经，求攒人品

多谢楼主的面经和大家的解题思路 太有用了！

fanlala 发表于 2017-12-11 09:42
抱歉，应该是我解释的不够通透

首先不需要排序；你的例子是1 3 5 7 24 60 80

这种方法是可以的。不过需要考虑重复数值的问题的话，不能用heap，得用map或者set可以处理重复的数据结构。

fanlala 发表于 2017-12-10 14:01
其实这题跟merge n sorted linkedlist是一样的：
一开始的最大sum肯定是所有的都加起来嘛，因为weight没 ...

但是感觉用你说的heap这种方法，时间复杂度会非常高。 n的k次方？

楼主居然不是背靠背两轮么？一轮就可以了？

luka77 发表于 2017-12-13 10:46
但是感觉用你说的heap这种方法，时间复杂度会非常高。 n的k次方？

我感觉是knnlogn？一共while循环k次，每次循环删除一个list里每个元素，一共n次，heap排序nlogn。。
求解答

马克一下 谢谢楼主！

LZ说的heap是用priority_queue然后自己定义一下comparator吗。。难道有什么别的简单的方法

这题就是combination的变体吧, 求不同组合, 如果组合的weight,符合要求就加入结果

prince123 发表于 2017-12-21 11:05
我感觉是knnlogn？一共while循环k次，每次循环删除一个list里每个元素，一共n次，heap排序nlogn。。
求 ...

嗯嗯，我觉得你说的是对的

gameboyying 发表于 2017-12-22 03:54
这题就是combination的变体吧, 求不同组合, 如果组合的weight,符合要求就加入结果

我也觉得，得到所有的combination然后加到heap里，最后pop出k个就行了。