正文

《编程之美》——寻找发帖“水王”学习与扩展

surimj  surimj  2022-09-23  499

关键词：

问题描述（难度 *）：

传说，Tango有一大“水王”，他不但喜欢发贴，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的Tango水王吗？

方法1：

先对ID列表进行排序，由于“水王ID”出现次数超过总次数的一半，则有序ID列表的第N/2项（从0开始编号）一定是“水王”的ID。算法复杂度为排序的复杂度O(N*log₂N)。

方法2：

避免排序。每次去掉两个不同的ID，不断缩小问题规模，而又可以保证水王的ID保持占总数的1/2以上，时间复杂度仅为O(N)。代码的写法也有技巧，并不是真正删除列表中的ID，而是使用一个计数器nTimes和一个Candidate记录ID来实现。在遍历一次列表的过程中，如果遇到和candidate相同的元素，则nTimes+1；如果遇到和candiate不同的元素，则计数器-1；如果计数器的值=0，则把下一个a[i]赋给candidate，相当于把之前的所有元素都删除了，这些元素是两两不同的；最后留下的candidate的值就是水王的ID。书中附的伪代码如下：

 1 Type Find(Type* ID, int N)  
 2 {  
 3     Type candidate;  
 4     int nTimes, i;  
 5     for(i = nTimes = 0; i < N; i++)  
 6     {  
 7         if(nTimes == 0)  
 8         {  
 9              candidate = ID[i], nTimes = 1;  
10         }  
11         else  
12         {  
13             if(candidate == ID[i])  
14                 nTimes++;  
15             else  
16                 nTimes--;  
17         }  
18   
19      }  
20     return candidate;  
21 }

View Code

扩展问题：

随着Tango的发展，管理员发现，“超级水王”没有了。统计结果表明，有3个发帖很多的ID，他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗？

同样采取方法2的思想，实现代码（C++）如下：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 /*
 5 
 6 扩展问题：假如有3个发帖很多的ID，他们的发帖总数都超过看1/4,快速找出他们的ID。
 7 
 8 思路：分别用三个计数器（T1，T2，T3）记录3个Candidate(C1,C2,C3)，如果出现相同元素，则对应的计数器+1，如果元素与三个Candidate都不相同，则三个计数器均-1；
 9 当计数器为0时，则将i++后的a[i]值赋给相应的Candidate，这样就相当于去掉了4（或4的整数倍）个不同的ID，使问题规模缩小，而3个Candidate所占的比例仍然超过1/4，
10 遍历一遍后则可得到所求的3个ID。
11 
12 */
13 
14 int main(int argc, char const *argv[])
15 {
16     int T1,T2,T3; //设置3个计时器
17     int C1,C2,C3; //3个candidate
18     int i;
19     int const N = 20; //总帖子数
20 
21     T1 = 0,T2 = 0,T3 = 0;
22     int a[N] = {1,1,4,3,1,1,2,2,3,3,4,1,2,1,2,3,3,3,2,2};    
23 
24     for(i = 0; i < N; i++)
25     {
26 
27         if(T1 == 0 || C1 == a[i]) //计时器=0时，C1 = a[i]，计数器+1；或者计数器不为0，C1 == a[i]时，前一句相当于没有改变，计数器+1
28         {  
29             C1 = a[i];
30             T1++;
31         }
32         else if(T2 == 0 || C2 == a[i])
33         {
34             C2 = a[i];
35             T2++;
36         }
37         else if(T3 == 0 || C3 == a[i])
38         {
39             C3 = a[i];
40             T3++;
41         }
42         else  //如果与三个candidate都不相同,三个计数器均-1
43         {                      
44             T1--;
45             T2--;
46             T3--;
47         }
48     }
49 
50     cout<<"C1 :"<<C1<<endl;
51     cout<<"C2 :"<<C2<<endl;
52     cout<<"C3 :"<<C3<<endl;
53 
54 
55     return 0;
56 }

寻找水王

学生都喜欢在某一个论坛上交流，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。如果你有一张当前论坛的帖子（包括回帖）列表，其中帖... 查看详情

寻找水王

一、问题描述　　三人行设计了一个灌水论坛。信息学院的学生都喜欢在上面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。　... 查看详情

寻找“水王”(代码片段)

...王吗？设计思想：通过记录每一个数字出现的次数，寻找出现次数最多的那个源代码：1i 查看详情

课堂作业之寻找水王

一、题目　　有一个大“水王”，他不仅喜欢发贴，还会回复其他ID发的每个帖子。该“水王”发帖数目超过了帖子总数的一半。如果有当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个... 查看详情

编程之美之高速寻找多个数满足给定条件

一、寻找三个数之和等于给定值分析：方法类似与2Sum。就是先对数组进行排序，时间复杂度为O(nlogn)，然后固定一个数，用两个指针进行遍历，找到三个数之和等于给定的值就可以，时间复杂度为O(n^2)。详细可提交于leetcode：http... 查看详情

课堂作业：找“水王”

...面交流灌水，传说在论坛上有一个“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子数目的一半。如果你有一张当前论坛的帖子（包括回帖）列表，其中帖子的作者的ID也在其... 查看详情

12.6水王(代码片段)

水王（课堂作业）

找水王

读《编程之美——微软技术面试心得》有感

?这两天我读了一下《编程之美——微软技术面试心得》，扩展了我很多思路。?其中对一个算法的分析，编写，思考改进，再提出扩展问题，再进行思考。这些步骤会锻炼我们的思维能力。?开头的序章也很有用，讲述了面试流程... 查看详情

找水王(代码片段)

找到一个发帖数超过帖子数目一半的用户“水王”设计思想：二分之一的思想，因为发帖数超过一半，所以按顺序走ID，把前后不同的两个ID都消除，name剩下的就是“水王”的ID因为这样想：如果帖子的顺序是：... 查看详情

寻找水王(代码片段)

packagewaterking;importjava.util.Scanner;/**寻找水王*/publicclasskingpublicstaticvoidmain(String[]args)int[]a=null;//存储帖子idScannersc=newScanner(System.in);System.out.println("请输入帖子总个数：");intsum=sc.nextI 查看详情

《架构之美》阅读笔记06

...重读经典二、笔记总结（1）面向对象与面向函数函数式编程能够更好的实现模块化设计。在面向对象的编程方式出现之后，我们发现面向对象的程序设计，特别是支持高级例程对象或者代理的现代形式包含了函数式编程，在保... 查看详情

寻找水王2(代码片段)

packagetest2;importjava.util.Scanner;/**寻找水王*/publicclasstest2publicstaticvoidmain(String[]args)int[]a=null;//存储帖子idScannersc=newScanner(System.in);System.out.println("请输入帖子总个数：");intnum=sc.nextInt( 查看详情

编程之美2.12高速寻找满足条件的两个数

这道题目的意思是，在一个数组中寻找两个数。使这两个数的和等于给定的数（找到随意一组就能够了）。题目读完之后，感觉这道题目还是非常easy的。就是遍历数组呗，走两遍，即能够在O(n2)时间复... 查看详情

编程之美之2.5寻找最大的k个数

【题目】有很多无序的数，从中找出最大的K个数。假定他们都不相等。【解法一】如果数据不是很多，例如在几千个左右，我们可以排一下序，从中找出最大的K个数。排序可以选择快速排序或者堆排序[cpp] viewpla... 查看详情

课堂练习——找水王

软件工程个人作业之——谁是水王？

设计思想：水王是发帖和回帖最多的那个，总数会超过总贴数的一半还要多，我的思想是，当两个挨着的人发帖的id不同就进行抵消，最后剩下来的就是总数超过一半的“水王”的id;代码实现:packagedemo;publicclasstext1{ staticint[]a={2,2,... 查看详情