水王问题

求论坛的最大水王

题目： 论坛有一水王，发帖量超过总帖子数的一半。。。如何快速的寻找水王的ID？

分析： 与寻找一个数组中出现次数超过总的个数一半的元素类似。依次遍历数组，每次删除一对元素，这对元素值不同。那么剩下的部分水王的地位不变。不断缩小问题，最终剩下很小的一部分，可以找到水王。

int FindKing(int* ID,int n) {int candidate;int nTime,i;nTime = 0;for(int i=0;i<n;i++){if(nTime ==0 ){candidate = ID[i];nTime = 1;}else{if(candidate ==ID[i])nTime ++;elsenTime --;}}return candidate; }

---

求最大的三个水王

题目： 随着论坛的发展，管理员发现水王没有了，但是统计结果表明，有三个发帖很多的ID。据统计他们的发帖数量超过了1/4，你能从发帖列表中快速找到他们吗？

分析： 沿用上次消除的思想，定义三个计数器和三个嫌疑水王，比较三个ID，如果不相同，就排除，如果相同，那么计数器加一。嫌疑水王ID都与其它水军ID进行抵消最后剩下的就是三个水王。

int candidate1; int candidate2; int candidate3; void Find(int* ID, int N) {int nTimes1 = 0 ;int nTimes2 = 0 ;int nTimes3 = 0 ;int i;for( i = 0; i < N; i++){if (nTimes1 == 0){candidate1 = ID[i], nTimes1 = 1;}else{if (candidate1 == ID[i]){nTimes1++;}else{if (nTimes2 == 0){candidate2 = ID[i], nTimes2 = 1;}else{if (candidate2 == ID[i]){nTimes2++;}else{if (nTimes3 == 0){candidate3 = ID[i], nTimes3 = 1;}else{if (candidate3 == ID[i]){nTimes3++;}else{nTimes1--;nTimes2--;nTimes3--;}}}}}}} }

总结

以上是生活随笔为你收集整理的水王问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。