距离上次更新本文已经过去了 386 天，文章部分内容可能已经过时，请注意甄别

[TOC]

题目说明

来源：剑指 Offer 56 - I. 数组中数字出现的次数
另外，260 只出现以此的数字 3 这道题和本题是一样的。2023 年再回头看，剑指 offer 在 leatcode 上改名成 lcr 了。所以本文标题也更新一下。

难度：中等

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O (n)，空间复杂度是 O (1)。

示例 1：

plaintext
1
2
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

plaintext
1
2
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：2 <= nums.length <= 10000

方法 1：常规做法

最容易想到的常规做法：

  • 先对该数组进行 qsort 排序，再用 for 循环遍历，找到数组中下标 i 和 i+1 不相等的哪一项，这一项 i 即为只出现了一次的数字。

  • 若最末尾的数是目标数，需要进行判断并 break，防止越界访问数组

如果你不了解 qsort，可以看这篇博客学习一下👉点我

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//方法1，太过简单，不够高级
cmp(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;
}

int* singleNumbers(int* nums, int numsSize, int* returnSize) {
    int* result = (int*)calloc(2, sizeof(int));
    int k = 0;

    qsort(nums, numsSize, sizeof(int), cmp);//对原数组进行排序

    int i = 0;
    for (i = 0; i < numsSize; i++)
    {
        if (i == numsSize-1)//如果i是末尾数，需要进行判断
        {
            result[k] = nums[i];
            break;
        }

        if (nums[i] == nums[i + 1])
        {
            i ++;
        }
        else
        {
            result[k] = nums[i];
            k++;
        }
    }


    *returnSize = 2;
    return result;
}

image-20220306173023648

方法 2：异或求解

复习一下位操作符

很尬尴的是，本人对位操作符和移位操作符并不熟悉。经常把它们记混。几次测试的时候，涉及到这两个操作符的题目就是瞎蒙。

后来发现位操作符和移位操作符似乎是测试中经常考察的对象，这里建议大家一定要把它们弄懂！

语句操作符对应结果
c = a & b& 按位与全 1 为 1，否则 0
c = a | b| 按位或有 1 为 1，否则 0
c = a ^ b^ 按位异或相同为 0，不同为 1

题解

异或有一个特点，a^a=0，a^0=a

image-20220306170537760

案例 1

plaintext
1
2
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

以题目所给参考 2 为例

plaintext
1
1^2^10^4^1^4^3^3 = 2^10

可以看到，当我们把所给数据全部异或在一起的时候，其结果正好是我们需要的两个数相异或。

但是我们好像并没有什么好的办法把已经异或了的两个数拆开

这时候就需要对待查找的数据进行分组

  • 分组的目的：让两个单身狗分开到两组数据中
  • 这两组数据，除两个单身狗外，其他数字都出现了两次
plaintext
1
2
1 1 3 3 4 4 2
10

为什么是这么分的呢？

plaintext
1
2
3
10: 1010
2:  0010
10^2=1000

可见单身狗 10 和 2 之间，源码第四位才有差别

plaintext
1
2
3
4
5
1： 0001
2： 0010
3： 0011
4： 0100
10：1010

这时候我们就可以通过第 4 位的差距，将数据分为两组

  • 第一组是 1~4，它们的第 4 位都是 0

  • 第二组是 10，只有它的第四位是 1

再根据前面异或的特点，对这两组数字进行异或操作，即可得到单生狗 10 和 2

plaintext
1
2
1^1^3^3^4^4^2 = 2
10 = 10

案例 2

上面这组数据有些特殊，第二组里面只有 10 一个数字

我们再来看一组数据

plaintext
1
1 2 3 4 5 1 2 3 4 6

这一组数据中，单身狗是 5 和 6

plaintext
1
2
3
5：0101
6：0110
5^6 = 0011

可见 5 和 6 的源码中，第一、二位都有区别

这里我们取第一位来分类即可

plaintext
1
2
3
4
5
6
1：0001
2：0010
3：0011
4：0100
5：0101
6：0110

二进制第一位为 1 的数，放入一组

plaintext
1
2
1 1 3 3 5
2 2 4 4 6

对它们进行异或操作，就可以得到单身狗 5 和 6

敲代码

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//方法2-异或
int* singleNumbers(int* nums, int numsSize, int* returnSize) {
	//1.全部异或在一起
    int i = 0;
    int k = 0;
    for (i = 0; i < numsSize; i++)
    {
        k ^= nums[i];
        //4^1^4^6 = 1^6
    }
    //2.判断k的二进制第几位是1
    int set = 0;
    for (i = 0; i < 32; i++)
    {
        if (((k >> i) & 1) == 1)//注意操作符优先级
        {
            set = i;//第i位为1
            break;
        }
    }
    //3.以第set位为1进行分组，可以将这两个数分开
    int n = 0;
    int m = 0;
    for (i = 0; i < numsSize; i++)
    {
        if (((nums[i] >> set) & 1) == 1)
        {
            n ^= nums[i];
        }
        else
        {
            m ^= nums[i];
        }
    }

    int* result = (int*)calloc(2, sizeof(int));
    //返回的数组必须用动态内存管理来创建
    result[0] = n;
    result[1] = m;
    *returnSize = 2;
    return result;
}

验证

自己整一个 main 函数来测试一下代码是否能达到要求，成功！

做接口题的时候，如果出现输出错误的情况，可以自己写一个 main 函数并调试来找出错误

image-20220306172530543

可以看到，运行的用时远远小于方法 1 的用时

击败了 92.9% 的用户！

image-20220306172614335

你学会了吗😍

如果这篇博客对你有帮助，点个👍再走呗～

摸鱼之发现另外一道一样的题

https://leetcode.cn/problems/single-number-iii/submissions/

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        //1.全部异或在一起
        int numsSize=nums.size();
        int i = 0;
        int k = 0;
        for (i = 0; i < numsSize; i++)
        {
            k ^= nums[i];
            //4^1^4^6 = 1^6
        }
        //2.判断k的二进制第几位是1
        int set = 0;
        for (i = 0; i < 32; i++)
        {
            if (((k >> i) & 1) == 1)//注意操作符优先级
            {
                set = i;//第i位为1
                break;
            }
        }
        //3.以第set位为1进行分组，可以将这两个数分开
        int n = 0;
        int m = 0;
        for (i = 0; i < numsSize; i++)
        {
            if (((nums[i] >> set) & 1) == 1)
            {
                n ^= nums[i];
            }
            else
            {
                m ^= nums[i];
            }
        }

        vector<int> retV;
        retV.push_back(n);
        retV.push_back(m);
        return retV;
    }
};