10亿个数找所有相似的数字对

给10亿个64位无符号整型数，定义每个数的bit位有三位以内的不同认为是相似的，输出所有相似的pair。要求时间复杂度尽可能低。
面试官后来说可以每16位分组，但是我还是没想明白，求大佬们指点。


#面试题#
全部评论
要建倒排索引的
点赞 回复 分享
发布于 2020-04-14 09:29
n:=1e9, 想到一种O(254081n)的 首先从概率角度讲两个数相似的几率为无限接近于0, 我直觉上觉得10亿个数中每一个都需要与其他数进行比较,  不过一个确定的无符号64位数a, 与a相似的数就只有254081个 然后还可以在O(1)时间内找出10亿个数里面有没有目标数: 因为unsigned int 64可以hash成unsigned int 32,  因此内存上搞一个(2**32)bit大小的数组也就是512MB, 就能在O(1)判断数在不在10亿个unsigned int64中，判断完这个数就在数组中删除它以免重复。此外如果这个题目需要输出重复的数对，那光输出就得O(n^2)，所以我认为输出数对不需要考虑重复情况。
点赞 回复 分享
发布于 2020-04-14 02:04

相关推荐

2025-12-30 15:54
柠檬微趣_数据库内核测试工程师(准入职员工)
柠檬微趣内推，柠檬微趣内推码
面经：暑假投递，面试时间线拉的比较长自我介绍实习经历介绍问了我他们公司有什么产品，让我说一款的细节设置，以及和竞品的细节差异在这个游戏设计一个中秋节主题关卡，应该怎么设计，什么思路？现在的关卡设置有什么需要改进的地方？休闲游戏的目标客户群体？有什么理解？休闲游戏符合设置付费点？什么品类的游戏是经久不衰的？🍋【柠檬微趣26届秋招】火热开启！一周极速Offer，职等柠来！✔ 研发发行《宾果消消消》《浪漫餐厅》《梦幻旅行》等爆款手游✔ 中国手游发行商出海收入排行榜Top 5✔ 合成手游赛道全球收入No.1的发行商📍 工作地点：北京市西城区🔥 秋招亮点✅ 岗位全覆盖：游戏开发、数据分析、游戏策划...
点赞 评论 收藏
分享
2025-12-29 15:19
银河通用_数据产品经理(准入职员工)
点赞 评论 收藏
分享
2025-11-12 14:20
华南师范大学 Java
211硕
0offer 今年Java行情也太难了
程序员花海：另外面试的时候可以把不会的问题记下来 总结一个知识库 之后回看 其实一个项目中能问的面试题也就那么些 多面试多总结就好
点赞 评论 收藏
分享
2025-11-19 17:28
济南大学 Java
点赞 评论 收藏
分享
评论
点赞
2
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 对2025年忏悔 #
9988次浏览 186人参与
# 机械/制造每日一题 #
82061次浏览 1430人参与
# 一人说一家双休的公司 #
13900次浏览 150人参与
# 非技术2023笔面经 #
316879次浏览 2685人参与
# 实习没人带，苟住还是跑路？ #
18765次浏览 342人参与
# 机械求职避坑tips #
82599次浏览 537人参与
# 工作中，努力重要还是选择重要？ #
248378次浏览 2412人参与
# 如果秋招能重来，我会____ #
79627次浏览 471人参与
# 应届生，你找到工作了吗 #
97555次浏览 596人参与
# 面试紧张时你会有什么表现？ #
21126次浏览 154人参与
# 为了找工作你投递了多少公司？ #
99503次浏览 685人参与
# 春招前还要继续实习吗？ #
12425次浏览 137人参与
# 每个月的工资都是怎么分配的？ #
81686次浏览 665人参与
# 虾皮求职进展汇总 #
362628次浏览 2767人参与
# 影石Insta360求职进展汇总 #
169346次浏览 1345人参与
# 哪些公司笔/面试难度大？ #
7478次浏览 35人参与
# AI时代，哪些岗位最容易被淘汰 #
25980次浏览 223人参与
# 你面试被问到过哪些不会的问题？ #
107273次浏览 1879人参与
# 秋招被确诊为…… #
280433次浏览 1589人参与
# 大疆的机械笔试比去年难吗 #
96324次浏览 767人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务