寻找发帖“水王”
在编程之美中有《寻找发帖“水王”》这么一题，这题书上提供了一个比较好的解法。对于某个元素超过总数N的1/M这类问题有一个通用的方法来解决。试看这样的操作：每次取出M个不同的元素，然后求解余下元素中超过总数1/M的元素。最终将能剩下M-1个元素，超过总数的1/M的元素肯定在其中，计算一下这些元素的数量即可得到解。总的时间复杂度最少能达到O(NMlogM)，下面代码实现了这个思路。

#include <iostream>using namespace std;struct item {int key;int cnt;};int most_frequent(int A[], int N, int val[], int M){struct item *tab = new struct item[M+1];if (tab) {for (int i = 0; i <= M; i++) {tab[i].key = 0;tab[i].cnt = 0;}for (int i = 0; i < N; i++) {for (int j = 0; j <= M; j++) {if (tab[j].cnt == 0) {tab[j].key = A[i];tab[j].cnt = 1;break;}if (tab[j].key == A[i]) {tab[j].cnt += 1;break;}}for (int j = 0; j <= M; j++) {for (int k = j + 1; k <= M; k++) {if (tab[j].cnt < tab[k].cnt) {swap(tab[j].key, tab[k].key);swap(tab[j].cnt, tab[k].cnt);}}}if (tab[M].cnt > 0) {int cnt = tab[M].cnt;for (int j = 0; j <= M; j++) {tab[j].cnt -= cnt;}}}for (int i = 0; i < M; i++) {val[i] = tab[i].key;}delete [] tab;}return M;}int main(){const int M = 4;int A[] = {1,1,2,3,4,4,4};int V[M];most_frequent(A, sizeof(A)/sizeof(A[0]), V, M);cout << "[";for (int i = 0; i < M; i++) {cout << V[i];if (i != M-1) {cout << ", ";}}cout << "]" << endl;return 0;}