-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathJz28.java
More file actions
122 lines (107 loc) · 2.85 KB
/
Jz28.java
File metadata and controls
122 lines (107 loc) · 2.85 KB
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
package com.cpucode.java.simple;
import java.util.HashMap;
import java.util.Map;
import java.util.Arrays;
/**
* 题目描述
* 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
* 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
* 示例1
* 输入
* [1,2,3,2,2,2,5,4,2]
* 返回值
* 2
*
* @author : cpucode
* @Date : 2021/1/20
* @Time : 14:41
* @Github : https://github.com/CPU-Code
* @CSDN : https://blog.csdn.net/qq_44226094
*/
public class Jz28 {
public int MoreThanHalfNum_Solution(int [] array) {
Map<Integer, Integer> map = new HashMap<>(array.length + 1);
for(int i = 0; i < array.length; i++){
/**
* 查询是否有这个key
* */
if(map.containsKey(array[i])){
/**
* 有出现就加一
* */
map.put(array[i], map.get(array[i]) + 1);
} else{
/**
* 第一次出现这个key
* */
map.put(array[i], 1);
}
/**
* 查询是否大于数组一半
* */
if(map.get(array[i]) > (array.length/2)){
return array[i];
}
}
return 0;
}
public int MoreThanHalfNum_Solution1(int [] array) {
/**
* 排序
* */
Arrays.sort(array);
int count = 0;
/**
* 中间下标, 如果众数大于一半, 就绝对在中间
* */
int half = array.length/2;
for(int num : array){
if(num == array[half]){
/**
* 记录中间值的数量
* */
count++;
}
}
if(count > half){
return array[half];
}else{
return 0;
}
}
public int MoreThanHalfNum_Solution2(int [] array) {
int cond = -1;
int cnt = 0;
for(int num : array){
if(cnt == 0){
/**
* 找到新的众数
* */
cond = num;
cnt++;
}else{
if(cond == num){
/**
* 和众数一样
* */
cnt++;
}else{
/**
* 和众数不一样
* */
cnt--;
}
}
}
cnt = 0;
for(int num : array){
if(num == cond){
cnt++;
}
if(cnt > array.length/2){
return cond;
}
}
return 0;
}
}