LeetCode majority-element

给定一个大小为 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
25
26
27
28
class Solution {
public:
int majorityElement1(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[int(nums.size()/2)];
}

int majorityElement2(vector<int>& nums) {
unordered_map<int,int> mp;
for ( auto x : nums ) {
if( (++mp[x]) > nums.size() / 2 )
return x;
}
return -1;
}

int majorityElement3(vector<int>& nums) {
int count = 1;
int res = nums[0];
for (int i = 1; i < nums.size(); ++i) {
if (count == 0 ) {
res = nums[i];
}
res == nums[i] ? ++count : --count;
}
return res;
}
};

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×