forked from algorithmzuo/algorithmbasic2020
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCode03_KM.java
More file actions
159 lines (148 loc) · 3.68 KB
/
Code03_KM.java
File metadata and controls
159 lines (148 loc) · 3.68 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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
package class02;
import java.util.HashMap;
import java.util.HashSet;
// 输入一定能够保证，数组中所有的数都出现了M次，只有一种数出现了K次
// 1 <= K < M
// 返回这种数
public class Code03_KM {
public static int test(int[] arr, int k, int m) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : arr) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
int ans = 0;
for (int num : map.keySet()) {
if (map.get(num) == k) {
ans = num;
break;
}
}
return ans;
}
public static HashMap<Integer, Integer> map = new HashMap<>();
// 请保证arr中，只有一种数出现了K次，其他数都出现了M次
public static int onlyKTimes(int[] arr, int k, int m) {
if (map.size() == 0) {
mapCreater(map);
}
int[] t = new int[32];
// t[0] 0位置的1出现了几个
// t[i] i位置的1出现了几个
for (int num : arr) {
while (num != 0) {
int rightOne = num & (-num);
t[map.get(rightOne)]++;
num ^= rightOne;
}
}
int ans = 0;
// 如果这个出现了K次的数，就是0
// 那么下面代码中的 : ans |= (1 << i);
// 就不会发生
// 那么ans就会一直维持0，最后返回0，也是对的！
for (int i = 0; i < 32; i++) {
if (t[i] % m != 0) {
ans |= (1 << i);
}
}
return ans;
}
public static void mapCreater(HashMap<Integer, Integer> map) {
int value = 1;
for (int i = 0; i < 32; i++) {
map.put(value, i);
value <<= 1;
}
}
// 更简洁的写法
public static int km(int[] arr, int k, int m) {
int[] help = new int[32];
for (int num : arr) {
for (int i = 0; i < 32; i++) {
help[i] += (num >> i) & 1;
}
}
int ans = 0;
for (int i = 0; i < 32; i++) {
help[i] %= m;
if (help[i] != 0) {
ans |= 1 << i;
}
}
return ans;
}
// 为了测试
public static int[] randomArray(int maxKinds, int range, int k, int m) {
int ktimeNum = randomNumber(range);
// 真命天子出现的次数
int times = k;
// 2
int numKinds = (int) (Math.random() * maxKinds) + 2;
// k * 1 + (numKinds - 1) * m
int[] arr = new int[times + (numKinds - 1) * m];
int index = 0;
for (; index < times; index++) {
arr[index] = ktimeNum;
}
numKinds--;
HashSet<Integer> set = new HashSet<>();
set.add(ktimeNum);
while (numKinds != 0) {
int curNum = 0;
do {
curNum = randomNumber(range);
} while (set.contains(curNum));
set.add(curNum);
numKinds--;
for (int i = 0; i < m; i++) {
arr[index++] = curNum;
}
}
// arr 填好了
for (int i = 0; i < arr.length; i++) {
// i 位置的数，我想随机和j位置的数做交换
int j = (int) (Math.random() * arr.length);// 0 ~ N-1
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
return arr;
}
// 为了测试
// [-range, +range]
public static int randomNumber(int range) {
return (int) (Math.random() * (range + 1)) - (int) (Math.random() * (range + 1));
}
// 为了测试
public static void main(String[] args) {
int kinds = 5;
int range = 30;
int testTime = 100000;
int max = 9;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int a = (int) (Math.random() * max) + 1; // a 1 ~ 9
int b = (int) (Math.random() * max) + 1; // b 1 ~ 9
int k = Math.min(a, b);
int m = Math.max(a, b);
// k < m
if (k == m) {
m++;
}
int[] arr = randomArray(kinds, range, k, m);
int ans1 = test(arr, k, m);
int ans2 = onlyKTimes(arr, k, m);
int ans3 = km(arr, k, m);
if (ans1 != ans2 || ans1 != ans3) {
System.out.println(ans1);
System.out.println(ans3);
System.out.println("出错了！");
}
}
System.out.println("测试结束");
}
}