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

要建倒排索引的

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)，所以我认为输出数对不需要考虑重复情况。