主元素问题

概述

给一个有 个元素的数列，保证有一个数 出现的次数 超过 ，求这个数。

做法

桶计数做法

桶计数做法是出现一个数，就把这个数出现次数 ，很好懂：

时间复杂度 。

但是这个做法很浪费空间，我们不推荐使用。

排序做法

显然，若一个数列存在主元素，那么这个主元素在排序后一定位于 的位置。

那么我们又有想法了：

看起来不错！ 的复杂度可还行？

下面介绍本问题的 解法。

主元素数列的特性

由于主元素的出现的次数超过 ，那么在不断的消掉两个不同的元素之后，最后一定剩下主元素。

输入时判断与上一次保存的输入是否相同，如不同则删除两数，这里用栈来实现。

再进行优化后，空间复杂度也可以降至 。