腾讯面试遇到的一道题，请各路大神帮忙看看

面试官说答案应该是O(logN)的复杂度，O(n)级别的就不需要的了。。。

#面试题目##腾讯#
全部评论
n很大时，重复数大于1000的复杂度和重复数大于1的复杂度没有区别，结合lowerbound和upperbound的这类二分是做不到log n的，思考n个有序数字中找出有重复的数字这个问题，假设每个数字重复1次，那么答案的复杂度是n/2，不管你用什么办法，输出答案的复杂度就已经超过log n了，所以，面试官复杂度估计是有误的。
1 回复 分享
发布于 2020-08-26 08:18
最差怎么可能是logn，楼上那个做法最好情况是全员1000，nlogk/k。
1 回复 分享
发布于 2020-08-26 07:29
二分
1 回复 分享
发布于 2020-08-25 23:37
可以尝试一下倍增法
点赞 回复 分享
发布于 2020-08-26 11:10
和剑指offer求旋转数组的最小值一样的做法，兄弟
点赞 回复 分享
发布于 2020-08-26 10:37
分治?每次二分成两半，判断中间交界的是不是，是就两半的加上交界的，不是就等于两半的加起来，应该是logN
点赞 回复 分享
发布于 2020-08-26 09:09
M
点赞 回复 分享
发布于 2020-08-26 09:03
leetcode有这道题，二分法，就是logn
点赞 回复 分享
发布于 2020-08-26 08:52
兄弟，写思路和算法复杂度，是指写伪代码还是直接说思路出来就可以哦？需要完成的把代码写出来吗？
点赞 回复 分享
发布于 2020-08-26 02:02
题目呢
点赞 回复 分享
发布于 2020-08-25 23:36
快排思路
点赞 回复 分享
发布于 2020-08-25 23:32

相关推荐

07-05 13:29
滴滴_运维开发工程师(准入职员工)
滴滴内推
测试面经：一面自我介绍tcp和udp的区别http和https的区别对测试的理解出了一个测试用例题：假设平台每天都可以创建活动，用户领取这些活动进行参与，加入需要限制每个用户每天参与活动的时间不能超过8个小时，如果超过，就不能再领取参与，请你设计一个测试用例mysql查询语句：有一个成绩表(学号，姓名，科目，分数)存有学生各科成绩，查询学生的总成绩并进行排名你做测试的优势有哪些你对滴滴出行平台怎么做测试开发一个算法题：有x个台阶，每次可以走1-x步，打印每种走法的步数明细你在实习中遇到什么困难，怎么解决的会不会git，git命令会不会linux，常用linux命令栈和堆⭐关于职场氛围：真的很爱...
点赞 评论 收藏
分享
07-09 11:53
山西农业大学 硬件产品经理
点赞 评论 收藏
分享
05-17 12:01
成都理工大学 Java
点赞 评论 收藏
分享
07-01 16:05
河南师范大学 Java
点赞 评论 收藏
分享
07-10 12:20
门头沟学院 前端工程师
点赞 评论 收藏
分享
评论
1
20
分享

招聘动态

查看更多

滴滴

2026届秋季校招提前批

米哈游2026校园招聘

技术提前批

小红书

REDstar提前批招聘

Touch CIB

数字兴业科技挑战赛

现代汽车前瞻技术研发挑战赛

26届投递链接合集

快手

快Star-X特别技术人才计划启动

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 你认为小厂实习有用吗？ #
14461次浏览 189人参与
# 面试官是我前女友 #
107205次浏览 731人参与
# 实习生的蛐蛐区 #
41488次浏览 333人参与
# 当你面对裁员会如何？ #
276152次浏览 2438人参与
# 计算机有哪些岗位值得去？ #
13361次浏览 134人参与
# lastday知无不言 #
57067次浏览 460人参与
# 在职场上，你最讨厌什么样的同事 #
14653次浏览 150人参与
# 推荐一首陪你工作的歌吧 #
14103次浏览 97人参与
# 说说你知道的学历厂 #
29084次浏览 179人参与
# 你找工作的时候用AI吗？ #
15264次浏览 194人参与
# 下班后的时间你怎么安排 #
7889次浏览 118人参与
# 哪一瞬间觉得自己长大了 #
7488次浏览 168人参与
# 携程求职进展汇总 #
559595次浏览 4258人参与
# 面试尴尬现场 #
24754次浏览 172人参与
# 工作后会跟朋友渐行渐远吗 #
30142次浏览 216人参与
# 中核求职进展汇总 #
20294次浏览 152人参与
# 社会教会你的第一课 #
30014次浏览 399人参与
# 多益网络工作体验 #
49766次浏览 280人参与
# 虾皮求职进展汇总 #
244343次浏览 1797人参与
# 神州信息工作体验 #
16174次浏览 75人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务