图森破电面

倒序浏览 · 2021-12-14 14:22:42

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

给4个sorted list，然后找到最小和（从4个list里各取一个数) 感觉medium到har

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

久了，记不清楚，也没表达清楚。。是第k个smallest sum。

来自APP · 2021-12-15 00:14:30

直接取每个list里面最小的数，然后加起来就和最小啊

我是不是理解错了😂

john博士 · 2021-12-15 00:26:13

不知道是不是理解有误，确实没感觉到有多难

richard_515 · 2021-12-15 04:00:29

每个list取第一个数，肯定是最小和，但是要求第k小的和，就需要拿list后面的数去换前面的数，交换的差值第k-1小就行。于是求出每个list后面一个数减去前面一个数的差值，放进heap，置换k-1次得到的4个数字加起来就行。

匿名用户-GXYZX *2022-5-16 05:28:55* · 2022-5-16 05:28:55

richard_515 发表于 2021-12-14 13:00
每个list取第一个数，肯定是最小和，但是要求第k小的和，就需要拿list后面的数去换前面的数，交换的差值第k ...

这个有必要用heap吗？这个已经sorted了，只要顺序扫描就可以吧？

Bobatech

the idea of Lettcode # 2 is similar to this question.