算法 | 如何用位运算从一堆数中寻找出现K次的数？

前言
本文主要介绍如何使用位运算从一堆数中寻找出现K次的数，这一堆数中有很多数出现了M次，只有一个数出现了K次，并且K是小于M的，另外要求额外空间复杂度为O(1)，时间复杂度为O(n)，那么该如何寻找出这个数呢？
例如，给出一个数组arr=[1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4]，K = 2，M = 3。在这个数组中，只有1这个元素出现了2次，其他的元素都出现了3次，现在要求使用位运算把1这个元素找出来。
思路分析
要求额外空间复杂度为O(1)，也就是说，我们只能创建有限的、固定的几个变量。
之前的几个寻找元素的题目都用到了异或运算来解决的，这个题目还能用异或运算吗？这个就不可以了，如果K是个偶数的话，用异或就直接给干废了。
我们知道，在Java中，int型的二进制的长度为32位。
如果把这个数组的所有元素都转成二进制，然后把二进制每个位置的数据相加，存放到一个长度为32位的数组中呢？
步骤
假如数组arr=[a,a,b,b,b,c,c,c,d,d,d]，K = 2，M = 3，要找出a这个元素。

先声明一个32位长度的数组tmp，里面的元素都默认为0。
循环遍历数组，并把数组中的每一个元素都转为二进制形式。
把每一个元素的二进制的值都累加到第1步声明的32位长度的数组中。
循环遍历这个32位长度的数组，判断数组中每个元素的数值和M的关系。
如果数组中的元素是M的整数倍，那么说明这个位置是没有a这个元素的。

循环arr数组过程如下：
第1个元素a的二进制假设为01111，累加到tmp数组中为，01111。
第2个元素a的二进制假设为01111，累加到tmp数组中为，02222。
第3个元素b的二进制假设为01000，累加到tmp数组中为，03222。
第3个元素b的二进制假设为01000，累加到tmp数组中为，04222。
......
以此类推，直到把所有的元素全部累加。
还原出现K次的数
tmp数组中的元素，假如为T，代表着arr数组中元素二进制位为1数出现的次数，他可能出现这几种组合：

T = 1 * K + 1 * M，所有元素在这个二进制位都为1。
T = 0 * K + 1 * M，只有出现M次的数，二进制位为1。
T = 0 * K + 0 * M，所有元素在这个二进制位都为0。
T = 1 * K + 0 * M，只有出现K次的数，二进制位为1。

从上面4种情况来看，因为 K < M，如果说T对M进行取模运算，取模为0的话，说明这个位置出现K次这个数的二进制位一定为0，否则为1。
所以，让tmp数组中的元素与M进行取模运算，就能识别出来出现K次的数的二进制位是什么情况，然后把二进制转成十进制就可以了，或者直接与0进行或运算，也能得到结果。
代码实现
经过上面的分析，来看下代码是如何实现的吧。
public class Code18_FindKTimes {
public static int findKTimes(int[] arr, int k, int m) {
int[] tmp = new int[32];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j <= 31; j++) {
tmp[j] += (arr[i] >> j) & 1;
}
}
int res = 0;
for (int i = 0; i < 32; i++) {
if (tmp[i] % m != 0) {
res |= (1 << i);
}
}
return res;
}
public static void main(String[] args) {
int[] arr = {11, 11, 11, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4};
int kNum = findKTimes(arr, 3, 4);
System.out.println(kNum);
}
}
复制代码
运行输出结果为：11。
(arr[i] >> j) & 1代码含义为判断arr[i]元素在第j位置的值是0还是1。
总结
本文主要介绍如何使用位运算从一堆数中寻找出现K次的数，利用了二进制、或运算、以及题目中M次的逻辑关系。
如果你有更好的办法，欢迎在评论区留言交流。