forked from DreamCats/java-notes
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathT39.java
More file actions
117 lines (107 loc) · 3.44 KB
/
Copy pathT39.java
File metadata and controls
117 lines (107 loc) · 3.44 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
package books;
import java.util.HashMap;
import java.util.Map;
/**
* @program JavaBooks
* @description: 数组中出现次数超过一半的数字
* @author: mf
* @create: 2019/09/20 10:01
*/
/*
数组中有一个数字出现的次数超过数组长度的一半
请找出这个数字。例如，输入一个长度为9的数组
{1,2,3,2,2,2,5,4,2},由于2在数组中出现了5
次，超过数组长度的一半，因此输出2
*/
public class T39 {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 2, 2, 2, 5, 4, 2};
// int res = moreThanHalfNum(arr);
// int res = moreThanHalfNum2(arr);
int res = moreThanHalfNum3(arr);
System.out.println(res);
}
// 哈希
private static int moreThanHalfNum3(int[] arr) {
HashMap<Integer, Integer> maps = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if (maps.containsKey(arr[i])) {
maps.put(arr[i], maps.get(arr[i]) + 1);
} else {
maps.put(arr[i], 1);
}
}
int length = arr.length >> 1;
// for (Map.Entry<Integer, Integer> entry : maps.entrySet()) {
// if (entry.getValue() > length) {
// return entry.getKey();
// }
// }
for (Integer key : maps.keySet()) {
if (maps.get(key) > length) {
return key;
}
}
return 0;
}
// 根据数组特性，相等++， 否则--， 毕竟最后剩最多次数的那个数
private static int moreThanHalfNum2(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int res = arr[0];
int times = 1;
for (int i = 1; i < arr.length; i++) {
if (times == 0) {
res = arr[i];
times = 1;
} else if (arr[i] == res) {
times++;
} else {
times--;
}
}
if (!checkMoreThanHalf(arr, res)) return 0;
return res;
}
// 采用快排的partition操作
//
private static int moreThanHalfNum(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int middle = (arr.length - 1) >> 1;
int partitionIndex = partition(arr, 0, arr.length - 1);
while (partitionIndex != middle) {
if (partitionIndex > middle) {
partitionIndex = partition(arr, 0, partitionIndex - 1);
} else {
partitionIndex = partition(arr, partitionIndex + 1, arr.length - 1);
}
}
int res = arr[middle];
if (!checkMoreThanHalf(arr, res)) res = 0;
return res;
}
private static boolean checkMoreThanHalf(int[] arr, int res) {
int times = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == res) times++;
}
boolean isMoreThanHalf = true;
if (times * 2 <= arr.length) isMoreThanHalf = false;
return isMoreThanHalf;
}
private static int partition(int[] arr, int left, int right) {
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index++);
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}