2020-04-22 10:44 已编辑牛客运营

关注

【每日一题】4月22日题目精讲二分

题号 NC14301
名称 K-th Number
来源 CCPC.2017哈尔滨站-重现赛
 戳我进入往期每日一题汇总贴~
往期每日一题题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题目让对数列A的每个区间求第K大，并将第k大插入到B中，再求B的第M大。
按题目一个区间一个区间求是肯定不行的，两次第k大十分丧病。
我们可以考虑把求值变成验证——
首先二分答案，每次二分的时候我们得到一个x，这个时候我们利用尺取，去得到第K大数大于x的区间一共有多少，如果大于m-1个说明x取小了。
那么第k大数大于x的区间一共有多少怎么求？第k大数大于x的其实也就是大于x的数至少有k个，当我们枚举区间左界L，我们可以从L往右扫描到第一个大于x的数有k个的的点R，右界在这个位置及其之后的区间大于x的点的个数都大于等于k个。而当L右移一个位置，R显然只会右移不会左移，所以L和R对每一个数字都只访问一遍，这样，时间复杂度是 $O(n)$ 的了。加上二分就是 $O（nlogn）$ 了。

看完邓老师的题解，记得自己去做题提高呀
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得 $\color{#FFD700}{10-50牛币}$ （依据题目难度和题解的内容而定）

本道题目4月29日中午12：00之前写的题解有获得牛币资格~

$\color{#FFA000}{Tips}$ .牛币兑换中心

牛客博客开通方式

如何开通牛客博客：https://www.nowcoder.com/discuss/202952
如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴

全部评论

推荐最新楼层

Kur1su

北京师范大学 C++

占坑啦啦啦~

1 回复分享

发布于 2020-04-21 11:06

⊙__⊙

浙大城市学院游戏后端

每次都被楼上占坑成功

点赞回复分享

发布于 2020-04-21 11:15

hnust_liuzelin

湖南科技大学 C++

https://blog.nowcoder.net/n/67ec11b9e3b84de69ca99745cbf6e36b

点赞回复分享

发布于 2020-04-21 12:08

一衍一

平顶山学院 C++

https://blog.nowcoder.net/n/78d26c8e9c6149fcbef1dbbf3bba300b

点赞回复分享

发布于 2020-04-21 12:11

精神病科黄主任

腾讯_微信_研发

https://blog.nowcoder.net/n/f1aab2f22e204857bad78a2087f483a4

点赞回复分享

发布于 2020-04-21 12:14

ThinkofBlank

东北大学 C++

https://blog.nowcoder.net/n/3a1dad4a9e4f4ac2993fa2d8e0e6c77f

点赞回复分享

发布于 2020-04-21 12:41

sunsetcolors

网易雷火_祝融工作室_游戏客户端开发

https://blog.nowcoder.net/n/0ea90bbf73b041c7bc3032f62df35817

点赞回复分享

发布于 2020-04-21 14:10

与人无语

湖南师范大学 C++

二分是我没想到的

https://blog.nowcoder.net/n/b4e5dc77efc849edb357e877695425c7

点赞回复分享

发布于 2020-04-21 14:19

吴国庆

哈尔滨理工大学 C++

https://blog.nowcoder.net/n/1ddb7296a54f4d49a0bbb451f6f38037

点赞回复分享

发布于 2020-04-21 14:32

luo想要个气球

广东技术师范大学 Java

https://blog.nowcoder.net/n/e58e6ceffbb545519f2d4a7ddb0682c6

点赞回复分享

发布于 2020-04-21 14:37

侃YE西

门头沟学院算法工程师

https://blog.nowcoder.net/n/266288af4d76496bba0d12cb823d8a04

点赞回复分享

发布于 2020-04-21 16:23

一只橘橘猫

桂林电子科技大学 C++

https://blog.nowcoder.net/n/de9c7e3534bc48e2b71dd2637e042bad

点赞回复分享

发布于 2020-04-21 16:43

⊙__⊙

浙大城市学院游戏后端

https://blog.nowcoder.net/n/0e7673e4780b4059a5fb14a1f289e8d0 这题好难，搞了我好久

点赞回复分享

发布于 2020-04-21 17:24

wxyww

山东大学 Java

https://blog.nowcoder.net/n/1a942266619443c882f376a116e60f2d

点赞回复分享

发布于 2020-04-21 19:13

hnust_yangyanjun

湖南科技大学 C++

https://blog.nowcoder.net/n/fbc3499dbd9b4de4bfd89f813933d01a

点赞回复分享

发布于 2020-04-21 19:57

rk_no

华南农业大学 C++

https://blog.nowcoder.net/n/f144ab125c4843c7a6a78a1c43138e89

点赞回复分享

发布于 2020-04-21 21:10

塞蒙尘

字节跳动_商业化技术_后端

https://blog.nowcoder.net/n/08cbadc2b29442aea97f1186ebaf06e2

点赞回复分享

发布于 2020-04-21 21:59

离ACM还有一定距离

门头沟学院 C++

https://blog.nowcoder.net/n/c6c4f2762c4142f29300819449c3a732

点赞回复分享

发布于 2020-04-21 22:05

sunrise__sunrise

中国海洋大学 C++

https://blog.nowcoder.net/n/d1ae407421844a43a87b1c341e159596

点赞回复分享

发布于 2020-04-22 00:34

19-hanhan

江西师范大学机器学习

https://blog.nowcoder.net/n/d78220c8048548acbd81a9fcd1391f0c 看了一天终于学会了

点赞回复分享

发布于 2020-04-22 16:09

02-23 10:19

东南大学后端

双非本末9硕勇闯Java实习——初识

和各位大佬汇报一下我的进度目前学完了JavaSE、JVM的内容，Java八股看了不少，还是有很大缺漏JVM看视频一遍，但基本没咋听懂，准备八股+AI问答学习了日常课程不多，有课上课，没课学习上午9点到工位开始看视频（黑马那一套）下午2点继续看视频，或研读Java八股，感觉还是挺充实的，抽一个多小时锻炼，不然身体遭不住晚上6点-10点看代码随想录，敲leetcode相关习题（之前从来没敲过）目前想着多背八股（有些看视频是真学不明白，直接嗯背了）3月投中小厂刷面试经验，之前从来没有面试过，一下子就大厂怕是脏了面评。等4月份技术栈成熟，面试经验丰富再碰瓷大厂，现阶段也不着急实习，毕竟学校还有课程（主...

我的实习求职记录牛客创作赏金赛

点赞评论收藏

02-19 07:57

山东大学嵌入式软件工程师

【行业解析4】：广义的体制内，公务员、事业编、央国企和高校的区别

起这个标题，本来是想把我了解的行业唠一遍的，结果又犯了爱画饼的毛病，懒得写了……最近老在抖音上刷到营销号说，现在的社会很像日本“被抛弃的一代人”，年轻人全民考公，挤破头进体制内……作为一个山东人，我寻思这个能唠。首先抛出问题：放到今天，体制内还是你求职就业的时候的首选项吗？或者说如果你选择了大厂，会把体制内当做自己的后路/退路吗？1，体制内的四大选择上面的问题放这儿先不谈，先讲讲什么是体制内。广义上讲，体制内可以分公务员、事业编、央国企、高校岗位。但其实细节上也是天差地别，比如事业编也分人的编还是岗的编，高校岗位也分事业编和合同工。2，行政编和事业编的区别这个好区分，直接关注两个要点：钱是谁发...

投递国家电网等公司10个岗位 > SAGIMA经验浅谈牛客激励计划

点赞评论收藏

02-06 15:42

小米集团_nlp算法工程师(实习员工)

兄弟们我是哪里问错hr了吗？

约面了，我想让他稍微再确定一下待遇和工作内容再考虑面不面试的

timeCrazy：鉴定完毕，她是脑袋尖尖的

点赞评论收藏

02-07 12:46

美团_核心本地商业_后端(实习员工)

26届双非简历求评价

又改了一版

烤点老白薯：可以除了名字都偷了

点赞评论收藏

02-21 16:31

长沙理工大学

双非本科软工大四学了C/C++和Qt，春招在即是深入服务端还是主攻QT开发？

大家好，今天分享一个很贴合目前校招时间段的提问：Up你好，本人双非本科大四，软件工程专业。大学前两年因为感觉前端好学，岗位也多选择学习前端。但那时比较懒散，课也多，所以前端也没有学多好。后来互联网寒冬，觉得出去不好找工作。就在大三下开始准备考研，但在去年10月份放弃考研（因为家里的一些事故，一个半月没有复习考研），处理好后，剩70多天感觉考不上值得上的学校。所以干脆准备就业，但感觉前端这个方向特别凉，于是换成了Linux c++方向（为此拒绝了一个前端实习）10月底到现在复习了c语言，学习了C++语法，特性，包括STL这些。学习了Linux系统编程进程线程，网络编程tcp/udp，多路转接，l...

牛客230000345号：毕业入坑两年，提点参考的东西吧，建议边找边备研，学历才是第一生产力，后期如果你要职业发展，这是最基本的几个了，工作和晋升除了项目经验，不就是比的派个人学历、吹牛能力和一堆头衔了(晋升的话，派系很重要)。工作方面，不了解服务端，但是你可以看招聘，其实相比来说qt在客户端和服务端都可以用到，而且跨平台兼容性好，而且qt不就是c+++吗(学好c++，用哪个框架都不头痛)，qt不只是给你个UI界面，封装的很多东西都是可以借鉴的。看你想去哪个城市，现在长沙软件行情不好，真心建议没上岸可以去深圳看看，长沙这边工资对标深圳砍半(眼泪流下来)，长沙不少大一点私企面试的也开始卷学历卷项目(双非泪奔)，如果想去国企你要能吹当然也可以(其实国企也就那12%的公积金了，并不稳定，但是稳定穷是肯定的)。想去好一点的，建议把基础打牢，学历一定要提高(长期发展一定要，国内还是不少地方学历论的)，如果有实习期建议能参与公司项目就参与，不然只会被拷打，最好从项目或者demo里把设计模式、指针、特性、模板、多线程实现并发并行、通讯协议、数据库这些基本的学会一部分，建议再学学qml和Linux，最好学一点嵌入式(Linux用在嵌入式板挺多的)，掌握一门脚本语言(Python，Python，Python)和git或者svn代码管理，没签合同(不是三方)，你还是校招生，校招只有一次(当然也可以说是本科一次，硕士一次，博士一次)，用了错过就没有了，好多公司最喜欢招应届生了，一张白纸(又便宜又容易被PUA)。最后，其实纠结这么多，不如第一份工作就选你最喜欢的编程语言、框架和操作系统，反正都是牛马，也不一定只吃一家喂的草