求序列里出现次数超过一半的数题解

如果对序列进行排序，那么相同的数会在序列中聚到一起，最坏情况下出现次数超过一半的数会聚到序列的两边，但因为出现次数超过一半，所以这个数会穿过序列的正中间。所以对于长度为$n$的序列$A$，出现次数超过一半的数一定是$A_\frac{n}{2}$。
时间复杂度为$O(n\log n)$。