题目

传言某论坛有一个“水王”，他的发帖数量超过总发帖数的一半，所有发帖ID都在一起，无序，如何最快找到这个”水王“的id？

思路 & 代码

排序，然后统计数量，这个可能是最基本的思路了，事实上数据库的count也是这么干的，但是这种做法的时间复杂度是
O（N*log2N + N）。
当然如果是有序的话，遍历一遍就够了，O（N）就可以了
但我们肯定不满足于此，如果有序，能否优化？
其实可以，因为有个前提条件，”水王“发帖数量超过一半，所以第N/2项肯定就是水王了，PS:不要在意是不是偶数这个小细节
so，如果有序，那就是O（1）

好的，言归正传，无序情况下，如何优化？
最优势的前提条件就是，超过一半，这个如何利用？
我们来想象下，如果去除两个不同的ID，那么”水王“是否依然保持超过一半？当然是的，so，伪代码如下：

Type Find(Type* IDs, int N) {
    Type candidate;
    int nTimes, i;
    for (i = nTimes = 0; i < N; i++) {
        if (nTimes == 0) {
            candidate = IDs[i], nTimes = 1;
        } else {
            if(candidate == IDs[i]) {
                nTimes ++;
            } else {
                nTimes --;
            }
        }
    }
    return candidate;
}

思考

小小的问题，看似简单，其实里面有一个最基本的道理，把问题简化，如此，无往不利

以上，欢迎大家指点、交流。

---

欢迎大家关注我的公众号

半亩房顶