LeetCode每日一练 —— 剑指Offer 56 数组中数字出现的次数

前言

Wassup guys！我是Edison

今天是 LeetCode 上的 剑指 Offer 56 - I. 数组中数字出现的次数

Let’s get it！

---

---

1. 题目描述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。

要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

示例 2：

2. 思路分析

做这道题之前，首先我们要明白一个东西，叫做 异或，那什么是异或呢？

1. 异或的性质

a ^ b：是将 a 和 b 的二进制的每一位进行运算，得出的数字。

运算的逻辑是：两个数对应的 bit 位，相同则为 0，不同则为 1。

2. 异或的规律

任何数和 本身 异或，结果都为 0；

任何数和 0 异或，结果是 本身；

3. 异或满足交换律。

即 a ^ b ^ c ，等价于 a ^ c ^ b；

注意： 如果你有一个数组，所有数都是出现了两次，只有一个数出现了一次，你可以对整个数组 循环异或，这样就能找到只出现了一次的那个数。

思路

基于上面 异或 的思想，其实我们只要把这个数组分成两部分，同时满足：

（1）相同的数字 被分到同一个部分。
 
（2）只出现一次的两个数字 被分到了不同的地方。

思路：

（1）先对数组中的所有数字进行一次异或，得到两个出现一次的数字的异或值。
 
（2）在异或结果中找到任意为 1 的位。
 
（3）根据这一位对所有的数字进行分组。
 
（4）在每个组内进行异或操作，得到两个数字。

实现

假设输入的数组是： [1，2，10，4，1，4，3，3]，其中只出现一次的两个数字分别是 2 和 10；

Step 1

第 1 步，先把 整个数组异或一遍，这样一定会得到一个新的数字，这个新数字就是两个只出现了一次的数字异或的结果，也就是 2 ^ 10 的结果：8，请记住这 8！

2： 0 0 1 0
10：1 0 1 0
x： 1 0 0 0

Step 2

第 2 步，8 的二进制为：1000，可以看到，这个里面有 0 也有 1，那这个 0 和这个 1 表示什么意思呢？

基于异或运算的性质：0 表示 bit 位相同，1 表示 bit 位不相同。

（异或运算：如果同一位的数字相同则为 0，不同则为 1）

Step 3

第 3 步，这个时候，我们要取得 8 的最低位是 1 的一个二进制数！

怎么取得最低位的这个二进制数呢？

很简单，只需要 x & (-x)；

&：两位同时为 1，结果才为 1，否则为 0

我们先计算 -x
1、根据x的二进制，按位取反
	x：0000 1000
  取反：1111 0111 // 反码

2、+1
	+1：1111 1000 // 补码

这个时候我们就得到了-x，接下来计算 x & (-x)
x： 		0000 1000
-x:	    	1111 1000
x & (-x)：	0000 1000

我们把这个新的二进制数（0000 1000）标记为 judgmentNum

Step 4

此时我们可以根据这个 数字 对 [1，2，10，4，1，4，3，3] 这个数组分组了。

先看看我们之前要分组的两个条件：

（1）相同的数字 被分到同一个部分。
 
（2）只出现一次的两个数字 被分到了不同的地方。

那我们是怎么满足这两个条件的呢？

我们只需要把和 judgmentNum 做 & 运算后为 0 的数字分到一组，不为 0 的数字分到另一组就可以了。

因为：

（1）对于出现了两次的同一个数字，因为他们是相同的，所以，他们和 judgmentNum 做 & 的结果也是相同的。这样，就满足了 条件 1；
 
（2）对于那两个个只出现了一次的数据，也就是 2 和 10 ，我们可以计算出它们和 judgmentNum 的 & 结果

2:				0000 0010
judgmentNum:	0000 1000
& 结果:			0000 0000

10:				0000 1010
judgmentNum:	0000 1000
& 结果:			0000 1000

可以明显的看出，2 的 & 结果为 0，但是 10 的 & 结果不是 0，这样就保证了它们被分到了不同的组

Step 5

到此为止，我们已经按照我们的计划，把原始数组，拆解成了我们想要的两个数组；

我们只需要对拆解后的两个数组，做一个循环，异或每一个元素，就可以了。

3. 综合分析

题解思路：

已知：两数相等异或结果为 0，一个数与 0 异或结果就等于其本身。
 
所以如果数组中只有一个出现一次的数，那么就只需要对所有的数进行异或就可以得到这个只出现一次的数，而本题中出现一次的数有两个。
 
所以，所有数异或的结果就是那两个只出现一次的数异或的结果。所以根据这个特性，我们就可以采用 分组 的方法解决此问题。
 
且分组要满足两个条件：1、两个相同的数必须出现在同一组；2、那两个只出现一次的数必须分配在不同的组。
 
这样我们分别对这两组数进行异或，就可以得到两个出现一次的数。那么，究竟应该怎么分组呢？
 
例如 [4,1,4,6]：全部异或的结果就是 1 和 6异或 的结果。就是 0001 和 0110 异或的结果为 0111。
 
其实我们不难发现，将该两个相同的数分配在一组是很容易实现的，我们只需要 固定一个二进制位，若这两个数在这个二进制位上的数是相同的，我们就把它分在同一组。
 
但是难点还是在 如何实现将两个只出现一次的数分配在不同的组里面？
 
往下分析，1 和 6 异或结果就是 0111，0111 这个二进制数中是 1 的二进制位暗含了什么个意思呢？
 
分析不难知道，二进制位是 1，就表示 1 和 6 在这个二进制位上的数是不同的。所以，这就是我们划分两个数到不同组的依据。
 
因为 0111 有 3 个二进制位都是 1，分别是第一位、第二位、第三位。这就表示了 1 和 6 的二进制数在第一、二、三位上的数是 不同 的。
 
我们假设就以第一个二进制位为划分标准。
 
数组中的数的第一个二进制位是 1 的就分为第一组。
 
数组中的数第一个二进制位是0的就划分为第二组。
 
这样就成功的将 1 和 6 分到了不同的组别中，而相同的数例如 4，因为 4 和 4 的第一个二进制位是必然相等的，这样也就实现了将两个相同的数划分到同一组。
 
最后只需要分别将这两个组进行异或，就可以得到我们要求的答案。

4. 代码实现

接口代码

int* singleNumbers(int* nums, int numsSize, int* returnSize){
    
    // 1.动态开辟一个数组newNums,用来保存只两个出现一次的数字
    int* newNums = (int*)malloc(2 * sizeof(int));

    // 2.将传过来的数组全部异或, 并用x保存起来，其x结果就是两个出现一次的数字异或的结果
    int i = 0;
    int x = 0; // 整个数组异或一遍的结果
    for (i = 0; i < numsSize; ++i) {
    
        x ^= nums[i]; 
    }

    // 3.计算出x二进制位第几位为1，用judgmentNum存起来
    int judgmentNum = 1; //初始位0001
    while ((judgmentNum & x) == 0) {
    
        //如果judgmentNum第一个二进制位不为1，就将judgmentNum左移一位0010，然后与x相与，判断judgmentNum第二位是否为一.
        //按此循环，知道找到judgmentNum的第一个为1的二进制位
        judgmentNum = judgmentNum << 1;
    }
    

    // 4.根据每个数的judgmentNum位置，进行分组，同为1的一组，同为0的一组
    int num1 = 0;
    int num2 = 0;
    for (i = 0; i < numsSize; ++i) {
    
        if (nums[i] & judgmentNum) {
    
            num1 ^= nums[i];
        }
        else {
    
            num2 ^= nums[i];
        }
    }

    // 5.将找到的数存到数组中
    newNums[0] = num1;
    newNums[1] = num2;
    *returnSize = 2;
    return newNums;
}

提交结果