leetcode 169. Majority Element 摩尔投票

缘起

群里看到一个有意思的问题 leetcode 169. Majority Element

简而言之就是O(n)时间求出出现次数>floor[n/2]的元素.

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一个大小为 n 的数组，找到其中的众数。这里的众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素,和统计学中
说的众数不一样.

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

这里介绍的是摩尔投票算法. 直接上代码吧, 代码比较简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
	int majorityElement(vector<int>& nums) {
		typedef vector<int>::iterator vit;
		int ans = -0x3f3f3f3f, cnt = 0;
		for (vit x = nums.begin(); x!=nums.end();x++)
		{
			if (*x==ans)
			{
				++cnt;
			}
			else
			{
				--cnt;
				if (!~cnt)
				{
					ans = *x;
					cnt = 1;
				}
			}
		}
		return ans;
	}
};

上述代码的主要思想是众数的个数超过一半, 所以不可能通过上述代码的将这个众数的cnt削为0. 因为没有数能干的过它.

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
24 ms
, 在所有 C++ 提交中击败了
77.32%
的用户
内存消耗 :
11 MB
, 在所有 C++ 提交中击败了
79.72%
的用户

后记

原本想过一个比较复杂的思路——就是桶排序也可以做这道题目. 先用个位过滤，再用十位过滤,…. 只要告诉我所有数的范围, 一旦把所有的位都过完，则剩下的那个桶中的数就是答案. 但是如果不给你位数呢? 这种桶排序的思想就嗝屁了的. 还是摩尔投票算法香!!!