LeetCode-数组中数字出现的次数（单身狗问题）

发表于

小知识，大挑战！本文正在参与「程序员必备小知识」创作活动

本文已参与 「掘力星计划」 ，赢取创作大礼包，挑战创作激励金

前言：🛫初来掘金！欢迎大佬们支持！相互学习，相互成长！

题目要求

一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。

方法：

  • 由于其他数都出现两遍，把这些数异或在一起，结果为0->，所以数组中所有元素异或起来，实际是两个单身狗异或的结果记为ret
  • 由于两个单身狗不相同，所有异或的结果至少有1个比特位为1 (异或特点：对应比特位，相同为0，不同为1)
  • 所以可以对ret逐位判断，找到为1的比特位所在的位置进行分组。pos：两个比特位不同的位置（即异或的结果对应的比特位为1的位置：可任意位置，只要对应比特位为1即可）
  • 把数组中所有元素的pos位为1的放在一组，把pos位为0的放在另一组。认为最低位是第0位

图解

image.png

image.png

image.png

选择二进制序列中的哪一个比特位为1进行分组没有关系，只要是选择异或结果的二进制序列中某一位为1的进行分组即可

代码

左移 << 右移

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
c复制代码int main()
{
    int arr[] = {1,1,2,5,6,5,7,8,7,8};
    int sz = sizeof(arr)/sizeof(arr[0]);
    int ret = 0;
    int i = 0;
    //将数组中的所有元素进行异或，得到的结果就是两个单身狗异或的结果
    for(i = 0;i<sz;i++)
    {
        ret^=arr[i];
    }
    //得到ret的二进制序列中比特位为1的位置
    int pos = 0;
    for(i = 0;i<32;i++)
    {
        //ret不断左移i位，与1相与，如果结果为1，说明该比特位为1
        if( ( (ret>>i) &1 ) ==1 )
        {
            pos = i;
            break;
        }
    }
    //将数组元素中二进制序列pos位为1的分到1组中，为0的分到另一组
    int m = 0;
    int n = 0;
    for(i = 0;i<sz;i++)
    {
        if( ( (arr[i] >>pos)&1 )== 1 )
        {
            //pos位置比特位为1和m异或
            m ^=arr[i];
        }
        else
        {
            //pos位置比特位为0和n异或
            n ^= arr[i];
        }
    }
    printf("%d %d\n",m,n);
    return 0;
}

leetcode题目：

链接：剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（LeetCode） (leetcode-cn.com)

image.png

函数接口：

1
2
3
4
5
6
arduino复制代码/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumbers(int* nums, int numsSize, int* returnSize){

}

思路和上面的基本一致，但是要注意，这个题目要重新开辟一个空间用来保存两个单身狗，所以数组只需开辟两个大小的空间即可。

题目已经明确说明，动态开辟的数组不用我们释放，由调用者自己释放。所以我们只需要返回该数组的起始地址即可！！

注意点：动态开辟的数组的元素最初要初始化为0，否则最初动态开辟的数组的两个元素都是随机值，这样进行分组异或的话就会出错

->为数组元素初始化可以使用：直接使用下标初始化：

e.g. arr[0] = 0 arr[1] = 0

也可以使用memeset()函数进行初始化！

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
44
c复制代码/**
 * Note: The returned array must be malloced, assume caller calls free(). ->后序我们不用释放，留个使用者释放
 */
int* singleNumbers(int* nums, int numsSize, int* returnSize){
        int i = 0;
        int ret = 0;
        //数组的元素进行异或，得到的结果就是两个单身狗异或的结果
        for(i = 0;i<numsSize;i++)
        {
            ret ^=nums[i];
        }
        //得到ret的二进制序列中比特位为1的位置pos
        int pos = 0;
        for(i = 0;i<32;i++)
        {
            //两个单身狗异或结果不断左移，直到找到比特位为1的位置
            if( ((ret>>i)&1) == 1 )
            {
                pos = i;
                break;
            }
        }
        //将数组元素比特位pos位置为1的分到一组，为0的分到另一组进行异或
        //开辟数组用来存储两个单身狗
        int* newarr = (int*)malloc(sizeof(int)*2);
        //注意：数组元素要初始化为0，否则不能通过，得到的是随机值
        newarr[0] = 0;
        newarr[1]= 0;
      for(i = 0;i<numsSize;i++)
    {
          //元素比特位pos位置为1的和数组第一个元素异或，为0的和数组第二个元素异或
        if( ((nums[i]>>pos)&1) == 1)
        {
            newarr[0] ^=nums[i];
        }
        else
        {
            newarr[1] ^=nums[i];
        }
    }
    //要返回数组中所含元素 ，让用户得知数组的元素个数。
    *returnSize = 2;
    return newarr;
}

好了，今天就到这儿吧，欢迎大佬们点赞、收藏、评论呀！笔者水平有限，欢迎各位大佬批评指正！再次感谢！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%