[TOC]

题目说明

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

难度：中等

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

示例 1：

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

示例 2：

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，可以看这篇博客学习一下👉点我

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

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

以题目所给参考2为例

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

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

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

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

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

为什么是这么分的呢？

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

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

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

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

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

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

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

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

案例2

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

我们再来看一组数据

1
1 2 3 4 5 1 2 3 4 6

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

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

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

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

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

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

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

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

敲代码

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/

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;
    }
};