<
查看: 275| 回复: 2
收起左侧

请教一道算法题!

一只大凡人 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   59
92%
8%
5

注册一亩三分地论坛,查看更多干货!

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

x

1.png

1.png

2.png

2.png

3.png

3.png
基础计算方法不难,就是loop所有bus可以载多少人就好。但是题目要求优化,test case里头有几万列数字,要求15秒内算好。hint说用更好的data structure来求,不知道各位大神能不能帮帮忙。

上一篇:南湾找学习搭子,刷题,系统设计
下一篇:北美小朋友学习结伴群, 欢迎加入
ubatuba 2024-4-8 06:55:11 来自APP | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   40062
93%
7%
3196
我的想法是可以优化到max(n,m)logn

首先把队列中的n个耐久度依次放进一个新数组,每次放进去的时候用二分法进行大小比较并且换位,最后在新数组中的位置代表在此之前多少人可以上车。另外储存一个hash,在每一个耐久度放进新数组之后,立即保存/刷新这个耐久度数值和位置的键值对。复杂度nlogn

第二步是对这个键值对按耐久度进行从小到大的排序。复杂度nlogn

然后再根据m个公交车到达的时刻,在第二步获得的数组中进行二分查找。复杂度mlogn

补充内容 (2024-04-08 06:55 +08:00):
抛砖引玉
回复

使用道具 举报

qingzh 2024-5-8 15:19:39 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   3
100%
0%
0
你可以抽象一下题目。
这道题等同于:
给定一个整型数组 p
给一个下标q[i], 问 p[i] - p[n] 里小于等于q[i]的整数的下标的最大值;比如p[n-1] < q[i] and p[n] > q[i],那就是n-1

这种题目一般都用单调栈
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

Advertisement
>
快速回复 返回顶部 返回列表