【每日一题】找到出现了K次的数

题目

一个数组中有一种数出现K次，其他数都出现了M次，M>1，K<M，找到出现了K次的数

**要求：**额外空间复杂度O(1)，时间复杂度O(N)

解析

因为有要求时间复杂度和空间复杂度，那么最好的解法仍然是使用位运算，这里使用的位运算比较巧妙

如果没有空间复杂度要求，可以直接使用哈希表，O(N)的空间复杂度

思路：

1. int类型的数拥有32位，那么创建一个32位的数组
2. 数组的每个位置记录的是数组中每个数的指定位上的值的累加
3. 然后遍历数组，判断其中的每个数是否为M的倍数，如果是，那么出现K次的数在该位上是0，如果不是并且余数为K,那么说明出现K次的数在该位上是1
4. 依次计算每个位上的数

代码实现

将arr数组中的每个数变成32位，然后将arr[i]在每一位上的数加和到t数组中，这样的话，因为t[x]上的每个数都是原始数组中数在x位上的加和，所以如果是M次的倍数，那么说明出现K次的那个数在该位上一定为0有（没有将这个数在该位上的数加进去，否则一定不是M的倍数，肯定会有余数，并且余数是K），这样对32位数组的每个数都计算之后，就知道了出现K次的数到底在哪个位上为1，这样的话，直接使用与运算就可以得到原始值

public static int onlyKTimes(int[] arr, int K, int M) {
    int[] t = new int[32];
    for (int i = 0; i < arr.length; i++) {
        // 计算每个数在32位上的每个位上的值的累加
        for (int j = 0; j < 32; j++) {
            t[j] += (arr[i] >> j) & 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < t.length; i++) {
        if(t[i] == 0) {
            continue;
        }
        // 如果该位置上的累加和取余为K,那么说明出现K次的数在该位置上为1
        if(t[i] % M == K) {
            ans |= (1 << i);
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20