problem
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.
Example 1:
1
2
3
4
5
6
| Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
|
approach1:
1
2
3
4
5
6
| class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
|
复杂度
approach2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int majorityElement(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
int res = 0;
for (int num : nums) {
if (!map.containsKey(num)) {
map.put(num, 1);
} else {
map.put(num, map.get(num) + 1);
}
if (map.get(num) > nums.length / 2) {
res = num;
break;
}
}
return res;
}
}
|
复杂度
approach3:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public int majorityElement(int[] nums) {
int res = 0;
int count = 0;
for (int num : nums) {
if (count == 0) {
res = num;
}
if (res != num) {
count--;
} else
count++;
}
return res;
}
}
|
复杂度
approach4:
分治算法