2020-07-03:有1亿个数字,其中有2个是重复的,快速找到它,时间和空间要最优

 福哥答案2020-07-03:

1.双重遍历。 时间复杂度是O(N^2)。

2.排序。 采用外部排序。时间复杂度是O(NlogN)。

3.遍历加哈希存储。 空间换时间,时间复杂度是O(N),空间复杂度是O(N)。这种方法适用于小数据量,在这里用明显不合适。

4.布隆过滤器。 根据公式计算,万分之一的失误率需要228M内存。个人感觉这种方法不太合适。

5.压缩位图。 根据我目前的分析,压缩位图适合稀疏存储,在这里用,效果不明显。32位整数总共有42亿个,这道题有1亿个数字,1/42算不算稀疏,就不得而知了。时间有限,没测试。

6.哈希分组。 这1亿个数字整数范围不限。 一个分组里有两个参数,一个参数保存数据,另一个参数保存个数DataCount。重复的数字一定在同一个分组中,然后对每一个分组进行遍历加哈希存储。如果DataCount过大,再次哈希分组。

7.位图。 32位整数范围,占用内存4G/8=512M。 最大值和最小值范围,占用内存 (max-min)/8+1,最小占用内存 1亿/8=不到12M。

结论:方法6和方法7都行。方法6适用的范围广,浮点数也行。方法7只适用于32位整数。


评论

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部