算法 | 如何用位运算从一堆数中寻找出现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这个元素。

1. 先声明一个32位长度的数组tmp，里面的元素都默认为0。
2. 循环遍历数组，并把数组中的每一个元素都转为二进制形式。
3. 把每一个元素的二进制的值都累加到第1步声明的32位长度的数组中。
4. 循环遍历这个32位长度的数组，判断数组中每个元素的数值和M的关系。
5. 如果数组中的元素是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数出现的次数，他可能出现这几种组合：

1. T = 1 * K + 1 * M，所有元素在这个二进制位都为1。
2. T = 0 * K + 1 * M，只有出现M次的数，二进制位为1。
3. T = 0 * K + 0 * M，所有元素在这个二进制位都为0。
4. 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次的逻辑关系。

如果你有更好的办法，欢迎在评论区留言交流。