当前位置: 首页 > 面试 > 正文

查找水军王–问题分析

关键字:
1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

随着网络时代到来,出现了一种新的职业“水军”。他们主要的工作就是给需要访问的网站提供访问。说白了就是职业刷信用人员,职业投票人员,职业评论人员。每天花大量时间在网上评论,制造虚假访问评价信息。对于这样的人员我们需要尽量挖出他们来。
d107_125854237
假设现在有一个刷虚假信用的水军人员。我们不知道他的ID,只知道他评论次数超过总评论数N的一半。现在我们需要抓出这个超级“水军王”

解法一

最直接的解法可能就是先排序,在有序情况下扫描一次计数就可以得到所求。也可以直接二分查找一次就可以确定水军,即取排好序的数组的中间值就为所求。则这样时间复杂度就为排序算法的时间复杂度。比值排序算法中最快的时间复杂度为O(log2(n)*n) ,包括堆排序和归并排序,快排的平均时间复杂度也为O(log2(n)*n),通常情况快排比堆排序快,因为建堆的消耗。对排序不多说了。

这里如果使用排序的方法是否还有可改进的呢?

这就的看ID的怎样的数据。这里就要再次提到一定要多留意题目的条件。上面稳重并未说ID数据的情况。

如果ID为连续的数字,并且有足够的内存那么可以考虑计数排序。其时间复杂度为O(n)。计数排序和bitmap的应用是一个原理:给定一个字符串数组,从中找出第一个只出现一次的字母

如果数据较多,不能全放入内存,则可以考虑 基数排序 时间复杂度为O(n*m)=O(n),m为单个ID的最大数字个数,入最长的ID为15412433那么m=8.

如果都不行,退而求其次可以考虑桶排序

前两种都是是使用空间来换时间。除去特殊情况下下可以改进排序算法到线性时间。那么是否有更通用的线性的时间的解法呢?

改进

再次审视题目,该水军贴超过一半,也就是说呈现下面的情况:
水军
将两者相减可以的到下图:
水军1
我们可以清晰的看到最右边的结果。相减后剩下的全爲水军论的ID。怎么能实现相减的操作呢,两个两个的取出来就可达到相减的目的。但是否可以随便取两个呢?在初始状态: count(水军王)>count(非水军)为安全状态。我们考虑如下情况:从数组中一次取出两个数

如果两个ID相同,那么可能这个ID是水军也可能不是;
如果两个ID不同,那么可能两个都不是水军ID,也可能其中有一个是水军ID,不可能两个都是水军ID,因为水军王只有一个。
情况1,将两个ID“相减”掉,那么可能两个相同的水军王ID被拿掉,这样有可能打破 count(水军王)>count(非水军) 的状态。导致最后的结果不正确。如果ID不是水军王的则不会打破安全状态。

情况2,如果两个ID都不是水军王的,那么把它们相减掉不会打破初始状态,如果情况是其中一个为水军王,一个不是。将两者相减掉,同样不会打破安全状态。

从上面的分析看。情况2始终能保证不打破安全状态。所以处在情况2是做“相减”是安全的,并可以的到正确结果。

那么算法就为:

遍历ID数组,取出两个ID如果不同就将两个都置空。如果两者相同,就寻找下一个不相同的ID,然后将两者置空。重复该过程,遍历一遍之后数组中非空的ID就全是水军王的ID了。

该算法也为线性时间,但没有解法一中线性排序中的限制,也不需要额外的存储空间。

本文固定链接: http://www.chepoo.com/find-navy-wang-state-machine.html | IT技术精华网

查找水军王–问题分析:等您坐沙发呢!

发表评论