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

向右看齐 2024-03-30 13:27 54阅读 0赞

### 前言 ###

本文主要介绍如何使用位运算从一堆数中寻找出现`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次的逻辑关系。

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