169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than n/2 times.
You may assume that the array is non-empty and the majority element always exist in the array.
思路1：
使用map来处理。
|
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
|
class
Solution {
public
:
int
majorityElement(vector<
int
>& nums) {
map<
int
,
int
> record;
for
(
int
i = 0; i < nums.size(); i++)
{
if
(record.find(nums[i]) == record.end())
{
record.insert(pair<
int
,
int
>(nums[i], 1));
if
(record[nums[i]] > nums.size() / 2)
{
return
nums[i];
}
}
else
{
record[nums[i]] += 1;
if
(record[nums[i]] > nums.size() / 2)
{
return
nums[i];
}
}
}
return
0;
}
};
|
思路2：
采用双循环
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
int
majorityElement(vector<
int
>& nums) {
int
hit = 0;
int
currentElem;
for
(
int
i = 0; i < nums.size(); i++)
{
currentElem = nums[i];
hit = 0;
for
(
int
j = 0; j < nums.size(); j++)
{
if
(nums[j] == currentElem)
{
hit++;
if
(hit > nums.size() / 2)
{
return
currentElem;
}
}
}
}
return
0;
}
|
本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1836477
