腾讯三面你会找半数以上的QQ号码吗

来源丨经授权转自涛歌依旧（ID：ai_taogeyijiu_）

作者丨涛哥

大家好，我是涛哥。

我们来看一道腾讯三面的面试题目，初看起来是挺简单的，其实不然。题目如下：

有2N个QQ号码，其中有一个QQ号码出现的次数大于N次，请找出这个QQ号码。要求：时空复杂度尽可能低。

有的人看到题目后就开始做，貌似也能得到正确结果，但无法通过腾讯的面试，主要是算法时空复杂度非最优。

涛哥手绘

排序是最容易想到的一种方法。由于目标QQ号码出现的次数超过数组长度的一半，所以排序后直接取中间元素就行。

腾讯会出这么简单的题目吗？有点搞笑！我们知道，基于比较的排序，时间复杂度能达到O(NlogN),但这不是最好的方法，无法通过腾讯的面试。

既然题目的意思是求出这个次数超过一半QQ号码，那就对次数进行计数吧，直接搞个hashmap就行了。此时，时间复杂度是O(N),但空间复杂度也是O(N)，无法通过腾讯的面试。

而且要注意到，使用计数法的时候，漏用了题目中的信息：出现次数大于N。显然，这是不合理的。这就跟你高考数学一样，你发现有个条件居然没用到，而你把题目做出来了，那是很值得怀疑的。

接下来，我们来介绍一种很巧妙的思路，即摩尔投票法，时间复杂度是O(N),空间复杂度是O(1)，可以满足腾讯面试的要求。思路是怎样的呢？

为了求超过半数的QQ号码，我们来看一种现实中的投票场景，以投票选择班长为例：

班级要开始选班长

要求半数以上通过

选出来的就是班长

我们先来看一种简单的情况：假如只有2个人A和B竞争班长这一职位。那么，在大家投票后，我们从投票箱中取数后，可以这样统计：

先抽一张票，如果是A，则记录当前胜利者为A，票数:1

再抽一张票，如果是A，则记录当前胜利者为A，票数:2

再抽一张票，如果是B，则抵消，记录当前胜利者为A，票数:1

再抽一张票，如果是B，则抵消，记录无当前胜利者

再抽一张票，如果是A，则记录当前胜利者为A，票数:1

...

如此循环，直到所有票统计完毕，最后有票的一方，就是胜利者，就是大家选出来的班长。这就是所谓的摩尔投票法。

如上只是两方进行PK,那么，当候选人为多人时，也可以使用类似的思路，这里的前提条件就是：一定存在多余半数票的候选人。

当多方进行PK时，占据着半数以上票数的班长，可以任性地抵消任何人的票，而且其他人之间的相互抵消也不会撼动班长的位置。

有的朋友看到这里，可能觉得有点绕，那么，我们一起来看看程序，并打印关键步骤，有兴趣的朋友可以对照程序和结果理解下。

腾讯主要使用C++编程，所以，我们就用C++来写代码，如下是对应的C++程序代码。solution函数详细地说明了摩尔投票过程：

#includeiostreamusingnamespacestd;intsolution(inta[],intn){intcount=0,value=a[0];for(inti=0;in;i++){printf("log,i=%d,count=%d,value=%d\n",i,count,value);if(count==0){value=a[i];}if(a[i]==value){count++;}else{count--;}}returnvalue;}intmain(){inta[]={6,2,5,3,4,2,2,2,2,5};intn=sizeof(a)/sizeof(a[0]);coutsolution(a,n)endl;return0;}

结果如下(经检验无误)：

log,i=0,count=0,value=6log,i=1,count=1,value=6log,i=2,count=0,value=6log,i=3,count=1,value=5log,i=4,count=0,value=5log,i=5,count=1,value=4log,i=6,count=0,value=4log,i=7,count=1,value=2log,i=8,count=2,value=2log,i=9,count=3,value=22

好的，先说这么多，希望大家在准备面试时，获得启发，举一反三，融会贯通，有所进步。今天先这样，咱们明天见。

1、超越Nginx！号称下一代Web服务器，用起来够优雅！

2、用Markdown做的PPT，真的太强了！

3、函数调用时底层发生了什么？

4、京东二面：高并发设计，都有哪些技术方案？

5、程序员最硬大佬，你绝对想不到！！！

点分享

点点赞

点在看