数组中数字出现的次数(中等难度)

目录

题目概述(中等难度)

思路与代码

思路展现

代码示例

题目概述(中等难度)

题目链接：

点我进入leetcode

思路与代码

思路展现

首先这道题目用到了原码，反码，补码的知识，有需要的小伙伴来看下这篇博客温习一下：

点我进入博客

题解可以看这个：

点我进入题解

那么先来看代码，然后我再对题解做一下补充

代码示例

class Solution {
   public int[] singleNumbers(int[] nums) {
    int bitmask = 0;
    //把数组中的所有元素全部都异或一遍
    for (int num : nums) {
        bitmask ^= num;
    }
    //因为异或运算的结果不一定都是2的n次幂，
    //在二进制中可能会有多个1，为了方便计算
    //我们只需保留其中的任何一个1，其他的都
    //让他变为0，这里保留的是最右边的1
    bitmask &= -bitmask;
    int[] rets = {0, 0};
    for (int num : nums) {
        //然后再把数组分为两部分，每部分在
        //分别异或
        if ((num & bitmask) == 0) {
            rets[0] ^= num;
        } else {
            rets[1] ^= num;
        }
    }
    return rets;
  }
}

时间复杂度：O(N)

空间复杂度：O(1)

解析：

for (int num : nums) {
        bitmask ^= num;
    }

这里就是将所有数字异或后，一定是只剩下最后两个只出现一次的数字，例如题解中给出的这组数字：[12，13，14，17，14，12]，

其中当将这组数组中的每个数字都异或完毕后，只剩下13^17，其异或后的结果为00000000 00000000 00000000 00011100，而我们代码中有一段是 bitmask &= -bitmask，所以说此时bitmask等于00000000 00000000 00000000 00011100，即为28，那么(-28)怎么算呢？注意：补码就是负数在计算机中的二进制表示方法，此时-28的原码为10000000 00000000 00000000 00011100，反码为11111111 11111111 11111111 11100011，那么补码为11111111 11111111 11111111 11100100,那么-bitmask = 11111111 11111111 11111111 11100100，而bitmask &= -bitmask即为下图所示：

可以看到此时bitmask的值为00000000 00000000 00000000 00000100，

可以看到我们最后一个1被保留住了，那么此时我们原数组就可以分为两组，一个是与此时的bitmask 与(&)后的结果为0的为一组，不为0的为一组(其实这块结果为不为0的原因跟每个数组中的数字的二进制转换后的倒数第三个数字是否为1还是0有关，为0的话就是0，为1的话就是非0，大家可以自己验证下)

所以说最后13和17一定再不同的组，然后12和14各自一定都在同一个组，12 ^ 12 = 0,14 ^ 14 = 0,所以数组中各自也只剩下了13和17，然后返回这个数组即可.