首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
AI面试、笔试、校招、雇品
HR免费试用AI面试
最新面试提效必备
登录
/
注册
Boundary
2017-05-16 19:31
中国人民解放军国防科技大学 C++
关注
已关注
取消关注
头条 一面挂 😂😂😂
问了两个算法题 1.给n个数,按字典序排序后,求第m个数 2. K个超长有序数组,求中位数 第一个题 勉强答对,但是面试官不满意 第二题就没答出来。主要是自己太菜了。 求各位大神,说说该怎么做吧
提示
全部评论
推荐
最新
楼层
盛夏de午夜
腾讯_研发
如果这个数是有范围的比如是int的范围,那就可以二分数的范围来查找。 1.那么可以假设用 (int最大值+int最小值)/2,作为假设中位数mid。 2.对于k个数组,均去查找mid所对应的位置,然后计算所有数组中比mid小和比mid大的数的个数lcont,rcount,因为是有序的,这个过程只要 klogn (n为数组长度)。 3.如果lcount==rcount ,那么mid就是真正的中位数 4.否则继续二分范围,比如lcount大,就让mid往左二分。 总的时间复杂度应该是log(数的范围)*k*logn 。log(数的范围) 一般不大,int的话就32
点赞
回复
分享
发布于 2017-05-17 10:33
客户端布道师字节分布
字节跳动_抖音搜索_tech lead
/** * Created by tlh on 2017/5/17. * 求两个排序数组合并后的中位数 * 设数组A和B,长度分别为m和n, 要求时间复杂度为O(log(m+n))。 * 用二分查找的思想,求合并后数组的第k个数。每次二分的过程都要设法舍弃掉数组的一部分,从而达到收敛缩小查找范围的效果。 * 从数组A和B分别取第k/2个数,当A[k/2-1] < B[k/2-1],则A的前k/2个元素必定在合并后的数组的前k个元素内,舍弃这A的前k/2个元素。 * 否则,舍弃B中前k/2个数。 * 接下来,递归在剩下的(m+n-k/2)的元素中找第(k-k/2)元素。 * https://www.jiuzhang.com/qa/1768/ */ public class MedianOfTwoSortedArrays { // 找到第K个元素 private int findKth(int[] A, int iA, int jA, int[] B, int iB, int jB, int k) { int m = jA - iA + 1; // 数组A的长度 int n = jB - iB + 1; // 数组B的长度 if (n < m) return findKth(B, iB, jB, A, iA, jA, k); // 保证数组A长度比数组B长度小 if (m == 0) return B[k - 1]; // 当较小的数组跑完了,返回数组B的第k个 if (k == 1) return Math.min(A[iA], B[iB]); // 返回第1个数 // 将k分成两部分 int lenA = Math.min(k / 2, m); // 取数组A的前lenA个元素 int lenB = k - lenA; // 取数组B的前lenB个元素 int pa = iA + lenA - 1; // 数组A的第lenA个元素 int pb = iB + lenB - 1; // 数组B的第lenB个元素 // 判断A[pa]和B[pb]的大小 if (A[pa] < B[pb]) return findKth(A, pa + 1, jA, B, iB, jB, k - lenA); // 舍弃数组A的前lenA个元素 else if (A[pa] > B[pb]) return findKth(A, iA, jA, B, pb + 1, jB, k - lenB); // 舍弃数组B的lenB个元素 else return A[pa]; // A[pa]或B[pb]就是对应的第k个数 } public float getMedian(int[] A, int[] B) { int totalLen = A.length + B.length; if ((totalLen & 1) == 1) { // 总数组长度为奇数 return findKth(A, 0, A.length - 1, B, 0, B.length - 1, totalLen / 2); } else { // 总数组长度为偶数 return (findKth(A, 0, A.length - 1, B, 0, B.length - 1, totalLen / 2) + findKth(A, 0, A.length - 1, B, 0, B.length - 1, totalLen / 2 + 1)) / 2.0f; } }
点赞
回复
分享
发布于 2017-05-17 18:20
清夜
北京邮电大学 C++
初步思考了一下,说一下自己的想法,如有误,轻喷... 对于第一题,字典序也是一种全序,这样的话使用partition的思路应该也可以O(log(n)),需要自己定义比较函数 对于第二题,应该是和2个数组的情况类似,相当于判断k个数组的第rank / k 个元素,找其中最小的淘汰元素。感觉实现起来也挺复杂,复杂度的话是在O(klogn)吧,不太确定 之前还想了使用堆的方法,就是使用一个最小堆存储数组首地址(指针),键值就是首元素值,然后每次取堆顶指针对应元素,递增指针,这样就改变了键值,调整堆,然后重复过程n/2次找到中位数 复杂度是O(klogk + n/2 * logk),只是比nk稍微好一点。。。。。。
点赞
回复
分享
发布于 2017-05-17 20:18
Boundary
楼主
中国人民解放军国防科技大学 C++
关于第一题, 是不是可以用堆排序? 定义某种比较函数cmp, 使得可以让11>101. 维护一个大小为m的大顶堆, 取前m个元素组成大顶堆, 遍历剩下的n-m个元素, 对于新的元素, 如果小于堆顶元素, 就替换堆顶元素,并调整堆, 否则就跳过该元素.继续比较下一个新的元素. 直到所有元素遍历完, 返回堆顶元素. 这样做的复杂度为O(nlog(m)). 但这种做法不适用于m很大的情况.
点赞
回复
分享
发布于 2017-05-17 19:22
sky_
University of Otago C++
第二道题,二分,
点赞
回复
分享
发布于 2017-05-17 17:20
东风造极
中国科大 Java
第一题,是这个题目?http://blog.csdn.net/fool _ran/article/details/40479059
点赞
回复
分享
发布于 2017-05-17 14:36
已注销
第一题的做法是: 将所有数字都在最后补充0,直到到位数相同,即位数不够的一直乘10,然后从小到大排序,第m个数字删去最后补充的0就是答案。 时间复杂度大约是n*logn,补0是复杂度为19*n,logn和19相差不大。
点赞
回复
分享
发布于 2017-05-17 12:10
静静卟噜卟噜
三峡大学 Java
为啥头条面试官都是女的
点赞
回复
分享
发布于 2017-05-17 08:53
zehua
西安交通大学 测试开发
我是来看大神怎么解的~
点赞
回复
分享
发布于 2017-05-16 23:47
C.C.
河北师范大学 iOS开发
第二个题目可以 维护两个堆来找中位数。
点赞
回复
分享
发布于 2017-05-16 22:21
盛夏de午夜
腾讯_研发
感觉你第一题答出来,第二题把k=2说清楚,应该没问题
点赞
回复
分享
发布于 2017-05-16 21:20
nicaiww
南京大学 Java
面试官是个女的?
点赞
回复
分享
发布于 2017-05-16 20:33
elop
南京航空航天大学 C++
都已经有序了?还求什么中位数
点赞
回复
分享
发布于 2017-05-16 20:25
牛客1973
重庆邮电大学 C++
楼主面的什么岗位?
点赞
回复
分享
发布于 2017-05-16 20:23
晴天158
Grab_Delv_服务端研发
第二题百度考了,不过是个简单版,给俩有序数组找中位数,要求复杂度log(数组和的长度)
点赞
回复
分享
发布于 2017-05-16 19:54
暂无评论,快来抢首评~
相关推荐
07-01 17:22
门头沟学院 运营
阿里的HR太强了吧!
淘天四面被震撼到了…面试官无比耐心的回答了我的反问,时长接近10分钟,全面介绍自身的OKR,部门整体情况,岗位职责,甚至还有对企业业务战略或者方向的思考,行业上的介绍…太有全局观了,仿佛上了一场宏大的课程但是又非常真实,不存在所谓的场面话。面试官在前面的问答中也非常的真诚,挖掘我自身的偏好和需求,循循善诱,也非常认同对于很多大学生而言所谓的职业发展规划多少会有点假大空厉害👍又学习了
阿里巴巴HR面291人在聊
点赞
评论
收藏
分享
不愿透露姓名的神秘牛友
06-27 20:15
字节面评脏了
还能挽救吗?找同学帮忙看了一下 字节怎么能如此对我
牛客26396789...:
你这是严重红线,被发现你自己永远进不去,你那个同学直接走人,你还敢宣扬
点赞
评论
收藏
分享
05-07 11:22
哈尔滨理工大学 Java
神州信息
这是多缺人 随便答的都过了
真烦好烦真烦:
牛友太有实力了
点赞
评论
收藏
分享
06-17 16:58
华南理工大学 C++
提前批这么早,原来是这样
星辰再现:
裁员给校招生腾地方
点赞
评论
收藏
分享
不愿透露姓名的神秘牛友
07-02 15:39
很担心现在hr的精神状态
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
2
收藏
分享
评论
提到的真题
返回内容
全站热榜
更多
1
...
实习周报不要再写流水账了
4.3W
2
...
算一笔账
9672
3
...
快手凉经
8819
4
...
毕业之后再也没人给我兜底了
8660
5
...
差点忘了以前是干嘛的,这个梗就是2025年最大的一坨
8463
6
...
工资还是得攒着
6257
7
...
高德-交易业务-Java日常-面经(OC)
4553
8
...
字节暑期实习刚oc要不要去
3858
9
...
这样的实习,我还有必要坚持下去吗?
3633
10
...
制造业提前批合集(个人版,大伙速投哇
3615
创作者周榜
更多
正在热议
更多
#
如何准备秋招
#
11095次浏览
192人参与
#
软开人,秋招你打算投哪些公司呢
#
100884次浏览
945人参与
#
现代汽车前瞻技术研发急速编程挑战赛
#
22332次浏览
185人参与
#
你觉得实习能学到东西吗
#
16083次浏览
381人参与
#
秋招什么时候开投比较合适?
#
6741次浏览
146人参与
#
实习,不懂就问
#
28040次浏览
450人参与
#
每个月的工资都是怎么分配的?
#
14269次浏览
312人参与
#
你觉得实习只能是打杂吗?
#
192422次浏览
1223人参与
#
你们公司几号发工资
#
18951次浏览
128人参与
#
你觉得现在还能进互联网吗?
#
4560次浏览
99人参与
#
非技术岗简历怎么写
#
216843次浏览
2918人参与
#
预测一下26届秋招形势
#
24628次浏览
239人参与
#
技术岗笔试题求解
#
75442次浏览
974人参与
#
你最近一次加班是什么时候?
#
67849次浏览
346人参与
#
高考出分的那一天,我__
#
16392次浏览
267人参与
#
聊聊你的职场新体验
#
161407次浏览
1391人参与
#
打工人的精神状态
#
54037次浏览
987人参与
#
大家实习每天都在干啥
#
82856次浏览
506人参与
#
米哈游工作体验
#
17763次浏览
116人参与
#
来聊聊你认为的薪资天花板是哪家?
#
30869次浏览
174人参与
#
机械实习一天多少钱合适?
#
28978次浏览
176人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务