Java教程

腾讯二面:20亿个QQ号码如何去重?

本文主要是介绍腾讯二面:20亿个QQ号码如何去重?,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

背景

之前找工作在腾讯面试遇到了一个很有意思的面试题,当时我记得现场还没有答出来,后来回家想了一下其实也没有那么难,而且还挺有意思的,今天做个整理分享给大家,希望对你有用

题目如下

文件中有20亿个QQ号码,请设计算法对QQ号码去重,相同的QQ号码仅保留一个,内存限制1G. 这个题目的意思应该很清楚了,不过为了方便大家理解,我画了一个比较有年代感的动画,希望大家喜欢https://img1.sycdn.imooc.com/61ad70000001353407120400.jpg

方法一

排序去重

其实说到去重,最简单的方法就是先排序,排序之后重复的QQ号码必然在一起,保留第一个,把其余重复的去掉就行,

整个过程如下面动画https://img1.sycdn.imooc.com/61ad70030001ec7104710229.jpg虽然这样可以解决问题,排序往往复杂度都很高,所以必定不是最优解

方法二

hashmap

如果排序的复杂对太高,那么直接用hashmap吧,hashmap的复杂度为O(1),思路其实很简单,就是直接把qq号记录到hashmap中,要是php的话直接记录在数组中就可以

hashMap[123] = true
hashMap[456] = true
hashMap[123] = true
hashMap[789] = true

由于hashmap的自动去重性质,所以自动变成了:

hashMap[123] = true
hashMap[456] = true
hashMap[789] = true

很显然,只有123,456,789存在,所以这也就是去重后的结果。

可是,面试官又要问你了:实际要存20亿QQ号码,1G的内存够分配这么多空间吗?显然不行,这样回答你还是无法通过腾讯面试

方法三

bitmap

来看绝招!我们可以对hashmap进行优化,采用bitmap这种数据结构,可以顺利地同时解决时间问题和空间问题。 

对bitmap有了大概的了解之后,我们直接把存在的qq号码对应的位置标记为1即可,下次查询只要对应的位为1,则为重复的qq号码,因为bitmap是一种非常省空间的数据结构,所以能够满足内存在1G之内的要求

好了,咱们今天先分享到这里

这篇关于腾讯二面:20亿个QQ号码如何去重?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!