Find发帖水王传说贴吧有一大“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的贴吧水王吗？ 先来思考一下 这个问题的意思就是从一个有很多ID的列表中找到一个数目超过总数一半的ID。也就是数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。 最明显的思路是遍历一遍，记下每个数出现的次数。可是对于一个无序的数组你会拙计的，时间复杂度是O（n^2）,空间复杂度是O（n）。如果你知道数组中最大的数是K，那可以利用array[k]++，两次遍历就可以求出来啦，时间复杂度是O（n），空间复杂度也是O（n），当然这方法是需要有条件的。 无序？ 那就给他排序啊，用快排排好序，再一次遍历就可以了（只需要以一个MaxTimes和WateringId就可以解决了，自己想一下）。时间复杂度T(n)=O(nlgn)+O(n)=O(nlgn)，空间复杂度是O（1）。其实压根就不需要再遍历，因为大于总数一半的ID肯定出现在N/2处，直接求得即可。时间复杂度也是T(n)=O(nlgn)，没什么本质的变化。 可不可以不排序呢？ 当然可以，我们可以用Hash表，一次遍历处理，一次遍历求的ID。 时间复杂度是O（n），空间复杂度也是O（n）。时间复杂度减少了，空间复杂度没变化。 可以减少空间复杂度吗？ ID的数量和一半有关系？这可以用分治策略来解决，把大问题化为若干子问题来解决。我们这样想，水王的ID比所有人的ID数目都多，如果我们删除一个水王的ID和一个其他人的ID，那最后剩余的ID就是水王的ID。当然我们不知道水王的ID是什么，可是只要我们删除的是不同的ID，那最后可能会剩很多ID，那就是水王的ID。基于这种思想，我们可以申请一个变长数组，首先放入第一个，然后从第二个ID开始判断是否和前一个相等，如果相等，那就删除已经存入的那个，否则加入。动态划分内存。时间复杂度是O（n），空间复杂度最好是O（1），最差同样是O（n）。。 其实呢，没必要非申请动态数组，这其实是一种思想。我们想象这是删除，可是我们并不删除，用一个变量来处理删除的事情，假设删除而已。用times记录ID的次数，用WateringId来记录水王的ID。当我们遍历的时候，如果此时数组中的ID和已经保存的水王ID一样，那times++，否则times--，如果times=0，我们需要保存此时的ID，并把times重新设为1。不同的相消，相同的累积而已。也就是说第一次times=0时记下当前ID作为水王的ID-，继续遍历，如果times=3则表示相等的ID有3个了，需要3个不同的ID才能使times变为0，times=0之后要记录新的ID作为水王哥的ID。遍历一遍足够找到水王的ID。 举个例子0，1，2，1，1，1 i=0，times=0 → WateringId=0，times=1； i=1，a[1]=1 ！= WateringId → times-- （times=0）； i=2，times=0 → WateringId=1，times=1； i=3，a[3]=2！= WateringId → times-- （times=0）； i=4，times=0 → WateringId=1， times++ （times=1）； i=5，a[5]=1=WateringId → times++ （times=2）； 此时WateringId = 1，YES，Done！ 不过不要忘了水王哥只是一个传说，不一定存在。所以最后要遍历一次，看看得出的水王ID的数量是不是大于N/2，是不是真的水王。 编码实现
int FindWateringId(int Id[],int M) { int WateringId; int times=0; if(0==M) //还要判断输入数目是否有效 return false; for(int i=0;i<M;i++) { if(times==0) { WateringId=Id[i]; times=1; } else { if(WateringId==Id[i]) times++; else times--; } } times=0; for(i=0;i<M;i++) //用来检测是否真的存在times>N/2的id { if(Id[i]==WateringId) times++; } if(times*2<=M) //ID数量大于N/2的水王不存在 IsExisted=0; else IsExisted=1; return WateringId; }
时间复杂度只是O(n)，空间复杂度只是O(1)而已。很nice的算法。 可是如果水王发的帖子数目刚好等于帖子总数的一半，那你还可以用上述方法解决吗？肯定行的通，换汤不换药而已，只要略加转变就可以完美解决。排序+统计可以，Hash也可以，删除的思想还行的通吗？对半?那删除完了不是把WateringId给弄没了吗？恩，也不一定啊。 如果水王的帖子数是总数的一半，那么总数必然是偶数，剩余的最后两个ID肯定有一个是水王的，不是全部，是其中一个！只需要最后加以判断即可。只需要稍微添加一些代码。int FindWateringId(int Id[],int M) { int WateringId; int times=0; if(0==M) //还要判断输入数目是否有效 return false; for(int i=0;i<M;i++) { if(times==0) { WateringId=Id[i]; times=1; } else { if(WateringId==Id[i]) times++; else times--; } } times=0; int WateringId2=Id[M-1]; //假设最后一个是水王，总数目是偶数 for(i=0;i<M;i++) { if(Id[i]==WateringId) times++; } if(times<M/2) WateringId=WateringId2; //这才是真的水王 times=0; for(i=0;i<M;i++) //用来检测是否真的存在times>N/2的id { if(Id[i]==WateringId) times++; } if(times*2<M) //ID数量大于N/2的水王不存在 IsExisted=0; else IsExisted=1; return WateringID; }
此版本同样适用于大于N/2的水王。 当然还有一种办法是用两个水王变量来解决这个问题。真假水王，最后谁的帖子多，谁就是真的水王，当然数目还要是满足times>=N/2的。这个也当然可以编码实现。int FindWateringId(int Id[],int M) { int WateringId; int FWateringId; int times=0; int Ftimes=0; if(0==M) //还要判断输入数目是否有效 return false; for(int i=0;i<M;i++) { if(times==0) { WateringId=Id[i]; times=1; } else if(Ftimes==0&&WateringId!=Id[i]) { //不能让WateringId和FWateringId相等 FWateringId=Id[i]; Ftimes=1; } else { if(WateringId==Id[i]) { times++; } else if(FWateringId==Id[i]) { Ftimes++; } else //同时减去，这下子 直接少了3个。 { times--; Ftimes--; } } } if(Ftimes>times) WateringId=FWateringId; //这才是真水王 times=0; for(i=0;i<M;i++) //用来检测是否真的存在times>N的id { if(Id[i]==WateringId) times++; } if(times*2<M) //ID数量大于N/2的水王不存在 IsExisted=0; else IsExisted=1; return WateringId; }
突然某一天，水王哥不见了，出现了3个发帖量超过总数1/4的水哥，你还能快速的找到他们吗？排序+统计完全可以搞定，无非是多了几个变量而已。类似a个发帖量超过总数1/b的问题都可以这么解决，这就好像一道ACM题了。有时间可以编码试试。 OK，水王问题解决！