给定一个数组，里面的只有一种数出现了 k 次，其余种类的数都出现了 m
次，要求找到这个出现了 k 次的数
首先可以考虑哈希表，记录每一个数的出现次数，最后遍历哈希表所有值，找到满足情况的数
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static int hashMapTest(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);
}
}
for (int num : map.keySet()) {
if (map.get(num) == k) {
return num;
}
}
return -1;
}
|
利用位运算
数组中所有的数都可以被表示为32位的整数
将数组中所有数字每一位的0或1情况进行统计
声明一个长度为32的数组，arr[i]记录 i 位上 1
出现了多少次，最后%m。
如果为0，说明这一位上出现k次的数那一位为0
如果不为0，说明这一位上出现k次的数那一位为1
最后将这个32位答案转化为十进制数就是答案
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
| public static int onlyKTimes(int[] arr, int k, int m) {
int[] numberBitSum = new int[32];
for (int num : arr) {
for (int i = 0; i < 32; i++) {
numberBitSum[i] += (num >> i) & 1;
}
}
int ans = 0;
for (int i = 0; i < 32; i++) {
ans |= (numberBitSum[i] % m != 0) ? (1 << i) : 0;
}
return ans;
}
|
额外空间复杂度：O(1)