【剑指offer系列刷题】第一篇——寻找单身狗

❤️《剑指offer》系列刷题——第一篇 ❤️
题目来源:数组中数字出现的次数(大家可以去测试一下自己的代码)
❤️ 博主码云gitee链接:https://gitee.com/byte-binxin ❤️

文章目录

  • 前言
  • 题目描述
  • 解题思路
  • 解题代码

【剑指offer系列刷题】第一篇——寻找单身狗_第1张图片


前言

这是《剑指offer》系列刷题第一篇文章,大家可以互相学习一下。

题目描述

题目描述

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

事例1:

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

事例2:

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

题目要求:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

解题思路
此题要求我们在一个数组中除两个数字之外,其他数字都出现了两次,让我们找到两个只出现一次的数字。这题对时间复杂度空间复杂度都有要求。空间复杂度是O(1)限制我们不能够额外开辟一块大于O(n)的空间。
这题我们考虑采用异或来解决这题,什么是异或?
两个数异或的结果是把他们的二进制数中对应的二进制位进行异或,相异为1,相同0
例:1和2异或

1^2
1 00000000 00000000 00000000 00000001
2 00000000 00000000 00000000 00000010
:: 00000000 00000000 00000000 00000011
1^2 = 3

  • 异或运算满足交换律:

a ^ b = b ^ a

  • 恒等率(0和任何数异或的结果都是那一个数):

a ^ 0 = a


解题思路

开始解题

  • 第一步:将数组中所用的数字与0异或一遍,得到的最终结果就是两个单身狗异或的结果。
    这句话如何理解呢?
    我们假设我们数组中的元素是[a,a,b,b,c,c,d,d,e,e,f,g]。其中的两个单身狗是f和g

【剑指offer系列刷题】第一篇——寻找单身狗_第2张图片
第二步
将这个数拆分开。
【剑指offer系列刷题】第一篇——寻找单身狗_第3张图片

解题代码

代码实现

int* singleNumbers(int* nums, int numsSize, int* returnSize){
     
    int t = 0;
    //第一步
    //将数组中所用的数字与x异或一遍
    //得到的结果就是两个单身狗异或的结果
    int i = 0;
    for (i = 0; i < numsSize; i++)
    {
     
        t ^= nums[i];
    }
    //第二步
    //分组
    //分组前准备  找到t的二级制数中为1的那一位,记录为m
    //为什么找为1的那一位呢?
    //因为1就说明两个单身狗这一位是不同的
    int m = 0;
    while (m<32)
    {
     
        if (t&(1<<m))
        {
     
            break;
        }
        m++;
    }
    //正式分组  将m位为1的分到一组,为0的分到另一组
    int x = 0;
    int y = 0;
    for (i = 0; i < numsSize; i++)
    {
     
        if (nums[i]&(1<<m))
        {
     
           //组1全部异或
           x ^= nums[i];
        }
        else
        {
     
        	//组2全部异或
            y ^= nums[i];
        }
    }

    *returnSize = 2;
    int* returnArray = (int*)malloc(sizeof(int)*2);
    returnArray[0] = x;
    returnArray[1] = y;

    return returnArray;
}

【剑指offer系列刷题】第一篇——寻找单身狗_第4张图片

你可能感兴趣的