题目
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
1
2 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2限制:
1 <= 数组长度 <= 50000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
三种解法:
- 对数组排序,取中位数下标
- unordered_multi_set 统计
- 摩尔投票法
投票法:
- 实际上是找到众数
- 假设数组第一个元素是众数,与众数不相同的数字应该使计数减一
- 当计数为0时,从数组首元素到当前元素的连续子数组中不存在唯一众数,因此剩余数组一定存在一个唯一众数,因此问题变成原问题的一个子问题
- 计数不为0时持续统计,此时当前选择的众数数量一定是最多的,并且遍历结束时计数一定为正