2021 后端开发笔记 21 异或运算算法题

题目：

一个数组中有一种数出现了K次，其他数出现了M次，
M > 1, K < M, 找到出现了K次的数。
如果有这个出现了K次的数返回这个数字，如果没有返回-1

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

解析：

这题重点是用逻辑运算来做，主要用到三个逻辑运算，逻辑或，逻辑与和异或

前情提要：

首先我们来复习一下这个三个运算的规则：
逻辑或：只要运算符左右两边有一个1结果就为1，否则为0 举个例子: 1或1 = 1， 1或0 = 1， 0或1 = 1， 0或0 = 0
逻辑与：需要运算符左右两遍都为1结果才为1，否则为0，只有当 1与1的时候结果才为1。
异或的意思是：相同为1，不同为0。

题目分析：

学过编程语言的都知道，整型的是32位的长度，他是用来存储一个数字的二进制形式，最高能存储32位的01，举个例子：
值为8的二进制是 1000，实际上是这样存储的：

0000 0000 0000 0000 0000 0000 0000 1000

不够的位数用0去填满，因此，我们可以设置一个长度为32的数组，将所有输入的整型全部以二进制的形式相加。

因此只要有1的部分它要么是m的整数倍，要么是对他取模之后余下k。

举个例子：比如m 是3， k是 1
出现三次的数字比如是2，出现一次的数字是6，因此相加就是

0 1 0
0 1 0
0 1 0
1 1 0

我们可以看到最后相加的结果是 1 4 0，因此如果我们用m对这三个数字取模，我们就能得到，1 1 0，只要对m取模不为0，那么它就是属于出现了k次的数字上面位！只要把这些取模不为0位数都提取出来，然后放到我们的32位的数组上面，我们就得到了这个数字的二进制，从而我们就知道这个数字什么了。

接下来我们来代码实现（中间有一个很坑的地方，接下来会说到）：

这一部分相对比较好理解，就是遍历所有的元素，然后将其对应的二进制位进行加和，重点说一下嵌套循环里面的
t[i] += (element >> i) & 1;
这里的意思是说数字的二进制形式向右移动一位，然后与上1，举个栗子，假设现在要填入的是7：

7的二进制形式是 111，1的二进制形式是001。因此当 i 为0的时候7是不用右移的，因此和1与上之后我们会得到 001，也就是1。

然后我们将7往右移一位，我们就会的得到 011，这时候我们在和1进行逻辑与的操作时 011 & 001，我们会得到一个1。

以此类推，这样我们能获得一个数所有位上的1。举个没有1的例子 010 与上 001 结果就是000。

// 请保证arr中，只有一种数出现了K次，其他数都出现了M次
    public static int onlyKTimes(int[] arr, int k, int m) {
        // 首先我们先申请一个32位的数组，用来加和我们所有数字的二进制
        int[] t = new int[32];

        // 遍历所有元素，将他的二进制形式上面的不为0的位进行加和
        for(int element: arr){
            for(int i = 0; i < 32; i++){
                t[i] += (element >> i) & 1;
            }
        }

然后我们尝试记录答案，循环我们创建的32位的列表，然后将每一个元素对m进行取余，如果不等于0并且等于k那么说明出现k次的数字在这里有1，然后将它填写到正确的二进制里面的位置。这是基础逻辑。

重点解释一下第二个if中的这个代码ans |= (1 << i);
因为ans等于0，所以它的32位的二进制上面都是0，因此我们需要把1移到正确的位置上填上去，我们这里用的是逻辑或，但是在或之前，我们需要将1向右移动至正确的位置。比如1出现在第二个位置，原本的ans的二进制是000，然后我们将1向左移动至第二个位置 000 -> 001 -> 010，然后和ans进行逻辑或我们就能得到010，然后以此类推，我们就能得到出现了k次的数字。

        int ans = 0; // 用来记录答案
        for(int i = 0; i < 32; i++){
            // 循环每一位，然后用m对它进行取模，
            // 如果为0就跳过，余k次的才是我们想找到的
            if(t[i] % m == 0){
                continue;
            }

            // 如果为等于k词说明我们找到了正确的位数
            if(t[i] % m == k){
                ans |= (1 << i);
            } else{
                // 不为0，但是也不等于k说明出现了在题目之外的数字返回 -1
                return -1;
            }
        }

最后一步，坑爹的来了！因为0在二进制位上的所有位数都是0，那么我们上面的代码第一个取模判断就会全部跳过，这样我们就不知道它是不是等于k的了。因此我们需要增加一个判断，对ans位0的时候遍历整个数组计算出现的次数是否等于k。

        if(ans == 0){
            int count = 0;
            for(int element: arr){
                if(element == 0){
                    count++;
                }
            }
            if(count == k){
                return ans;
            }
            return -1;
        }

最后返回答案

      return ans;
}

总结：时间复杂度是 $O(n)$ ，因为只是遍历了所有数字两遍，也就是 $O(2n)$ 。同时额外空间复杂度是O(1)，因为我们只申请了一个32位的数组，是固定长度的。

Reference： https://italk.mashibing.com/course/detail/cour_00004003