-
Notifications
You must be signed in to change notification settings - Fork 0
/
169.求众数.cpp
62 lines (57 loc) · 1.21 KB
/
169.求众数.cpp
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
56
57
58
59
60
61
/*
* @lc app=leetcode.cn id=169 lang=cpp
*
* [169] 求众数
*
* https://leetcode-cn.com/problems/majority-element/description/
*
* algorithms
* Easy (56.90%)
* Total Accepted: 26K
* Total Submissions: 44.9K
* Testcase Example: '[3,2,3]'
*
* 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
*
* 你可以假设数组是非空的,并且给定的数组总是存在众数。
*
* 示例 1:
*
* 输入: [3,2,3]
* 输出: 3
*
* 示例 2:
*
* 输入: [2,2,1,1,1,2,2]
* 输出: 2
*
*
*/
//法二。不修改数组的方法On
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.empty())
return 0;
int result=nums[0];
int times=1;
for(int i=1;i<nums.size();i++)
{
if(times==0)
{
result=nums[i];
times=1;
}
else if(nums[i]==result)
times++;
else times--;
}
int count=0;
for(const auto &i :nums)
{
if(i==result)
count++;
}
return count>nums.size()/2?result:0;
}
};