1.查找第k大的数：快速选择法，On（这里讲的都是时间复杂度）。快速选择法：由于快速排序每次排序都可以用On时间求出基准是第几大的数且左边都比基准小，右边都比基准大。若第一次求出基准是第i大，若ik，以i为右边界递归左边，每次减小一半查找范围，直到i==k，总共时间为On。2.查找最大k个数(k远小于n）：建一个大小为k的优先队列（小根堆），klogk，对于剩下的元素，若大于堆顶则拿掉堆顶最小的再插入，总共用nlogk的时间找到最大k个(堆顶为第k大的）。共计(n+k)logk<2nlogk=nlogk，k很小时视为On，k大时用方法4。3.频繁查找第k大的数（数组变化)：先用方法2找出原始数组最大k个数，klogk，若要新增元素，先对比堆顶，若大于堆顶则先移除堆顶再插入堆，这时堆顶为第k大的数。每次查找复杂度为logn。4.频繁查找第k大的数(k变化)：排序，nlogn，每次查找时间为O1。5.查找a~b之间的所有元素：先用快速排序法找到第a大和第b大的数，用On，再遍历一次，选出位于这两个数之间的数。总共On。6.频繁查找，数组和k同时变化：先建一个二叉搜索树nlogn，维护每个结点的子树大小，查k时从根节点开始，若小于左子树大小，直接进入左子树，否则k-=左子树大小后进入右子树，每次查找logn，每次插入时将经过的结点子树大小++，也是logn。7. 查找数据流的中位数：维护一个最大堆和一个最小堆，满足最大堆所有的数都小于最小堆的数，当两个堆数量相等时，中位数就是堆顶平均，若最大堆比最小堆大1，中位数就是最大堆顶，插入新元素时，奇数次考虑插入最大堆，若大于堆顶则插入最小堆，再把最小堆堆顶插入最大堆。偶数次类似。#面试题刺客退退退#

米哈游这笔试防君子不防小人啊。想一个小时过0%，骗分10分钟两题骗了115%以下都是我错误的思路别学。第二题看一眼，觉得要找最大矩形要用dp，一时想不起来，最大三角形估计要考虑很多情况，直接跳过了，后面只考虑了三角形也过了95%，但没想到全0的情况要不估计全过了（合着加了“或矩形”这几个字就是为了这一个情况）第三题属于是自己把自己玩死了。看了一下数据量直接放弃二次循环，对于数组中每个数y，用哈希表判断x/y在不在数组中，然后发现要考虑重复的数，又搞了个set记录重复的，然后发现一个set不够，又加了一个，然后发现要输出下标，赶紧把set改成map，然后发现输出的下标要加1，然后一堆哈希表把自己给弄晕了，总之到最后都没做出来，反倒直接二重循环还拿了20%

本来下午一个面试面了一个多小时脑子还是懵的，然后笔试第一题出的那种阅读理解我硬是看了半个小时才看懂，写了半天直到考试结束都不知道到底是哪里在越界😢

第一题统计相邻重复的，第二题遍历，若值与下标不同就把该值换到该去的下标那里，直到值与下标相同后i++。第三题考完才想出来的（主要是因为第二题想了一个小时越想越远都没注意到可以无视白的）。设ab为一个下标放了a，但本来这个下标应该放b的个数，同理有ac，bc，ba，ca，cb。这是假设把所有的a换到正确的位置，则ba和ca会变少，最多变为0，然后我也不知道了，应该多来几个if就能写出来

第三题，剩40分钟，一眼dp，想着时间复杂度也就1e9，多少能过几个用例吧，一顿操作15分钟过去了，通过0%。挣扎了5分钟决定用记忆化dfs，以前没用过，15分钟裤裤写完又发现不对又加了个哈希表调了半天，最后发现是升序那里搞错了，加了个判断，if（ans>tmp）ans=tmp。还错，时间没了，考完瞬间智商恢复发现ans没判断是否为空😑😑

被两道acm模式的链表题搞崩了，输入卡了半天，还有一道输入不带元素个数的，谁知道遇到这种怎么办

接到面试通知的来吱一声，我想看看有多少人和我一样投了没反应。我5号卡着雷锋日投的，到现在一点进展没有，最难受的是5号投的当天有个腾讯的电话我没接到，疑似HR，后面就一直没动静了

#牛客在线求职答疑中心# sap 成都vt项目都接到二面通知了吗，我在想是不是给我挂了没告诉我