1. 问题描述
给定一个数组arr，其中只有一个数字出现了K次，剩余的数字都出现M次，且$1\le K<M$，找出这个出现K次的数。
2. 暴力做法
使用哈希表统计每一个数出现的次数，最后遍历哈希表，返回出现K次的数。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| import java.util.HashMap;
public class AppearKTimesNumber {
public static int findKTimesNum(int[] arr, int k, int m) {
int len = arr.length, i = 0;
HashMap<Integer, Integer> countMap = new HashMap<>();
for(; i < len; ++i) {
Integer cnt = countMap.get(arr[i]);
if(cnt == null) cnt = 0;
++cnt;
countMap.put(arr[i], cnt);
}
for(Integer number : countMap.keySet())
if(countMap.get(number) == k) return number;
return -1;
}
}
|
时间复杂度$O(N)$，空间复杂度$O(N)$。
3. 最优解
int类型的底层是32位2进制数，我们统计所有数的二进制位上1的个数，我们假设答案ans上某一位是1，那么这个1要么出现$K$次，要么出现$K+xM(x \ge 0)$次，如果ans上的某一位是0，那么这一位上1的个数，只可能是$M$的倍数。因此我们可以根据某一位上1出现的次数能否被$M$整除，就可以知道答案ans这一位是0还是1，如下图所示：
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class AppearKTimesNumber2 {
public static int findKTimesNum(int[] arr, int k, int m) {
int len = arr.length, i = 0, j, ans = 0;
int[] bitCnt = new int[32];
for(; i < len; ++i)
for(j = 0; j < 32; ++j)
if((arr[i] & (1 << j)) != 0) ++bitCnt[j];
for(j = 0; j < 32; ++j)
if(bitCnt[j] % m != 0) ans |= 1 << j;
return ans;
}
}
|
时间复杂度$O(N)$，空间复杂度$O(1)$。
4. 测试程序
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
| import java.util.Random;
import java.util.Arrays;
import java.util.HashSet;
public class AppearKTimesNumberTest {
public static void main(String[] args) {
int times = 100_0000, maxM = 10;
while(times-- > 0) {
Random r = new Random();
int m = r.nextInt(maxM) + 2;
int k = r.nextInt(m - 1) + 1;
int mTime = r.nextInt(10) + 1;
int size = m * mTime + k;
int[] arr1 = new int[size], arr2 = new int[size], arr3 = new int[size];
HashSet<Integer> set = new HashSet<>();
int j = 0;
for(int i = 0; i < mTime; ++i) {
int num = r.nextInt();
while(set.contains(num)) num = r.nextInt();
for(int x = 0; x < m; ++x) {
arr1[j] = arr2[j] = arr3[j] = num;
++j;
}
}
int num = r.nextInt();
while(set.contains(num)) num = r.nextInt();
for(int x = 0; x < k; ++x) {
arr1[j] = arr2[j] = arr3[j] = num;
++j;
}
int ans1 = AppearKTimesNumber.findKTimesNum(arr1, k, m);
int ans2 = AppearKTimesNumber2.findKTimesNum(arr2, k, m);
if(ans1 != ans2) {
System.out.println("Oops!, wrong answer, ans1 = " + ans1 + ", ans2 = " + ans2 + ", k = " + k + ", m = " + m);
System.out.println("Origin array: " + Arrays.toString(arr3));
return;
}
System.out.println("Testcase: " + times + " done!");
}
System.out.println("Test done successfully!");
}
}
|
5. 升级问题
给定一个数组arr，其中只有一个数字出现了N次，剩余的数字都出现M次，且$1\le N<M$，如果$N=K$，那么返回这个出现K次的数，否则返回-1。
这个题目只是出现次数不一定是$K$次了，做法和上面的最优解大致相同，只是有一个小细节，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class AppearKTimesNumber3 {
public static int findKTimesNum(int[] arr, int k, int m) {
int len = arr.length, i = 0, j, ans = 0;
int[] bitCnt = new int[32];
for(; i < len; ++i)
for(j = 0; j < 32; ++j)
if((arr[i] & (1 << j)) != 0) ++bitCnt[j];
for(j = 0; j < 32; ++j) {
int mod = bitCnt[j] % m;
if(mod == k) ans |= 1 << j;
else if(mod != 0) return -1;
}
if(ans == 0) {
int cnt = 0;
for(int n: arr)
if(n == 0) ++cnt;
if(cnt != k) return -1;
}
return ans;
}
}
|
时间空间复杂度和上面的最优解一样
6. 升级问题测试程序
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
| import java.util.Random;
import java.util.Arrays;
import java.util.HashSet;
public class AppearKTimesNumberTest2 {
public static void main(String[] args) {
int times = 100_0000, maxM = 10;
while(times-- > 0) {
Random r = new Random();
int m = r.nextInt(maxM) + 2;
int k = r.nextInt(m - 1) + 1;
int mTime = r.nextInt(10) + 1;
int realK = r.nextInt(2) == 0 ? k + 1 : k;
int size = m * mTime + realK;
int[] arr1 = new int[size], arr2 = new int[size], arr3 = new int[size];
HashSet<Integer> set = new HashSet<>();
int j = 0;
for(int i = 0; i < mTime; ++i) {
int num = r.nextInt();
while(set.contains(num)) num = r.nextInt();
for(int x = 0; x < m; ++x) {
arr1[j] = arr2[j] = arr3[j] = num;
++j;
}
}
int num = r.nextInt();
while(set.contains(num)) num = r.nextInt();
for(int x = 0; x < realK; ++x) {
arr1[j] = arr2[j] = arr3[j] = num;
++j;
}
int ans1 = AppearKTimesNumber.findKTimesNum(arr1, k, m);
int ans2 = AppearKTimesNumber3.findKTimesNum(arr2, k, m);
if(ans1 != ans2) {
System.out.println("Oops!, wrong answer, ans1 = " + ans1 + ", ans2 = " + ans2 + ", k = " + k + ", m = " + m + ", realK: " + realK);
System.out.println("Origin array: " + Arrays.toString(arr3));
return;
}
System.out.println("Testcase: " + times + " done!");
}
System.out.println("Test done successfully!");
}
}
|
