主元素问题
概述¶
给一个有 n 个元素的数列,保证有一个数 a 出现的次数 超过 \dfrac n 2,求这个数。
做法¶
桶计数做法¶
桶计数做法是出现一个数,就把这个数出现次数 +1,很好懂:
1 2 3 4 5 6 7 8 9 10 |
|
时间复杂度 O(n+m)。
但是这个做法很浪费空间,我们不推荐使用。
排序做法¶
显然,若一个数列存在主元素,那么这个主元素在排序后一定位于 \dfrac{n}{2} 的位置。
那么我们又有想法了:
1 2 |
|
看起来不错!O(n\log n) 的复杂度可还行?
下面介绍本问题的 O(n) 解法。
主元素数列的特性¶
由于主元素的出现的次数超过 \dfrac n 2,那么在不断的消掉两个不同的元素之后,最后一定剩下主元素。
输入时判断与上一次保存的输入是否相同,如不同则删除两数,这里用栈来实现。
1 2 3 4 5 6 |
|
再进行优化后,空间复杂度也可以降至 O(1)。
1 2 3 4 5 6 7 8 9 10 11 |
|
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:SDLTF
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用