一. 题目
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
二. 思路
1. 初始思路
1). 遍历数组，然后使用hashmap存储每一个元素的出现次数
2). 当出现次数超过数组长度一般时，返回该元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import java.util.HashMap;
public class {
public int MoreThanHalfNum_Solution(int [] array) {
HashMap<Integer, Integer> countMap = new HashMap<>(array.length*2);
int maxNum, maxValue,tempNum,len = array.length;
for (int i = 0; i < len; i++) {
tempNum = countMap.get(array[i]) == null ? 1 : countMap.get(array[i]) + 1;
countMap.put(array[i], tempNum);
if (len / 2 < tempNum) {
return array[i];
}
}
return 0;
}
}
|
2. 参考思路
1). 主要思想是通过对*两个相邻、不同的元素进行消除，直到不能再消
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
29
30
|
public class {
public int MoreThanHalfNum_Solution(int [] array) {
if (array == null || array.length <= 0) {
return 0;
}
int num = 0,point = -1;
for (int i = 0; i < array.length; i++) {
if (num == 0) {
point = i;
num = 1;
} else if (array[point] != array[i]) {
num--;
} else {
num++;
}
}
if (num > 0) {
num = 0;
for (int i = 0; i < array.length; i++) {
if (array[point] == array[i]) {
num++;
}
}
}
return num > array.length / 2 ? array[point] : 0;
}
}
|
近期评论