剑指 Offer.39-数组中出现次数超过一半的数字
剑指 Offer.39-数组中出现次数超过一半的数字
题目链接
<剑指 Offer 39. 数组中出现次数超过一半的数字>
问题描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
个人想法（HashMap）
使用hash表存储每个数出现的次数，需要对数组进行两次遍历，时间复杂度为0(n)，空间复杂度为O(n)
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
| class Solution {
public int majorityElement(int[] nums) {
int target = 0;
if(nums.length % 2 == 0){
target = nums.length/2;
}else{
target = (nums.length/2);
}
HashMap<Integer,Integer> map = new HashMap<>();
for(int num:nums){
if(!map.containsKey(num)){
map.put(num,1);
}else{
map.put(num,map.get(num)+1);
}
}
Iterator<Map.Entry<Integer,Integer>> it = map.entrySet().iterator();
while(it.hasNext()){
Map.Entry<Integer,Integer> element = it.next();
if(element.getValue() > target){
return element.getKey();
}
}
return -1;
}
}
|
官方解法
使用摩尔投票算法，简单理解就是一种同归于尽的算法，首先选中数组中的第一个元素，从第二个元素开始进行遍历，当第二个元素与第一个元素不同时，vote-1，相同则vote+1，最后遍历完成还存活的元素，将其视为出现次数最多的元素。二次遍历，确认其数量是否超过半数，若超过半数则返回该数字。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int majorityElement(int[] nums) {
int x = 0,votes = 0,count = 0;
for(int num:nums){
if(votes == 0)
x = num;
votes += num==x?1:-1;
}
for(int num:nums){
if(num == x){
count++;
}
}
return count > nums.length/2?x:0;
}
}
|