forked from algorithm024/algorithm024
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMajorityElement_169.java
More file actions
78 lines (70 loc) · 2.25 KB
/
Copy pathMajorityElement_169.java
File metadata and controls
78 lines (70 loc) · 2.25 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
import java.util.Arrays;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
public class MajorityElement_169 {
/**
* 出现次数大于 ⌊ n/2 ⌋ 的元素排完序后一定在数组的中间位置
* @param nums
* @return
*/
public int majorityElement1(int[] nums) {
Arrays.sort(nums);
return nums[nums.length >> 1];
}
/**
* 使用 HashMap 统计每个数字出现的次数，然后遍历 map 找到次数大于大于 ⌊ n/2 ⌋ 的元素
* @param nums
* @return
*/
public int majorityElement2(int[] nums) {
// 使用 boxed 将 int 类型的字段转成 Integer 类型
// 使用 Collectors.groupingBy 分组计数
Map<Integer, Long> map = Arrays.stream(nums).boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
int n = nums.length / 2;
// for (int key : map.keySet()) {
// if (map.get(key) > n ) {
// return key;
// }
// }
// 对以上代码执行效率优化
for (Map.Entry<Integer, Long> entry : map.entrySet())
if (entry.getValue() > n)
return entry.getKey();
return -1;
}
/**
* 分治算法，递归求解
*/
public int majorityElement3(int[] nums) {
return majorityElementRec(nums, 0, nums.length - 1);
}
private int majorityElementRec(int[] nums, int lo, int hi) {
if (lo == hi)
return nums[lo];
// 递归逻辑
int mid = (hi + lo) / 2;
int left = majorityElementRec(nums, lo, mid);
int right = majorityElementRec(nums, mid + 1, hi);
if (left == right) {
return left;
}
int leftCount = countInRange(nums, left, lo, hi);
int rightCount = countInRange(nums, right, lo, hi);
if (leftCount < rightCount) {
return right;
} else {
return left;
}
}
private int countInRange(int[] nums, int e, int lo, int hi) {
int res = 0;
for (int i = lo; i <= hi; i++) {
if (nums[i] == e) {
res++;
}
}
return res;
}
}