10亿个数找所有相似的数字对
给10亿个64位无符号整型数，定义每个数的bit位有三位以内的不同认为是相似的，输出所有相似的pair。要求时间复杂度尽可能低。
面试官后来说可以每16位分组，但是我还是没想明白，求大佬们指点。
2020-04-14 08:50 已编辑 北京邮电大学 算法工程师
关注
全部评论
狗傻
门头沟学院 算法工程师
要建倒排索引的
学!
门头沟学院 Java
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)，所以我认为输出数对不需要考虑重复情况。
相关推荐
点赞 评论 收藏
分享