leetcode 229. Majority Element II 摩尔投票

缘起

继续刷摩尔投票. leetcode 229. Majority Element II

分析

1
2
3
4
5
6
7
8
9
10
给出一个序列, 找出其中出现次数> floor(n/3) 的数.

Example 1:

Input: [3,2,3]
Output: [3]
Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

和【1】相比，这里的众数的定义改成了 > floor(n/3). 注意，这种数的个数不会>2, 这是显然的呀~

所以沿用【1】的思想，但是维护两个”众数”就行了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
	vector<int> majorityElement(vector<int>& nums) {
		vector<int> ans;
		typedef vector<int>::iterator vit;
		int ans1=-0x3f3f3f3f, ans2=-0x3f3f3f3f, cnt1=0, cnt2=0;
		for (vit x = nums.begin(); x!=nums.end(); x++)
		{
			if (ans1==*x)
			{
				++cnt1;
			}
			else if (ans2==*x)
			{
				++cnt2;
			}
			else if (!cnt1)
			{
				ans1 = *x;
				cnt1 = 1;
			}
			else if (!cnt2)
			{
				ans2 = *x;
				cnt2 = 1;
			}
			else
			{
				--cnt1;
				--cnt2;
			}
		} // 最后可能的答案就是ans1和ans2
		cnt1 = cnt2 = 0; // 重新统计, 看看ans1和ans2到底是不是答案
		for (vit x = nums.begin(); x!=nums.end(); x++)
		{
			if (*x==ans1)
			{
				cnt1++;
			}
			else if (*x == ans2)
			{
				cnt2++;
			}
		}
		if (cnt1>nums.size()/3)
		{
			ans.push_back(ans1);
		}
		if (cnt2>nums.size()/3)
		{
			ans.push_back(ans2);
		}
		return ans;
	}
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
执行用时 :
8 ms
, 在所有 C++ 提交中击败了
99.39%
的用户
内存消耗 :
10.5 MB
, 在所有 C++ 提交中击败了
58.46%
的用户执行用时 :
8 ms
, 在所有 C++ 提交中击败了
99.39%
的用户
内存消耗 :
10.5 MB
, 在所有 C++ 提交中击败了
58.46%
的用户

参考

【1】https://yfsyfs.github.io/2019/10/10/leetcode-169-Majority-Element-摩尔投票/