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

xavier 发布于2021-10-12 10:12 / 898人阅读

摘要：剑指系列刷题第一篇题目来源数组中数字出现的次数大家可以去测试一下自己的代码博主码云链接文章目录前言题目描述解题思路解题代码前言这是剑指系列刷题第一篇文章，大家可以互相学习一下。其中的两个单身狗是和。

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

文章目录

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

前言

这是《剑指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。

第二步
将这个数拆分开。

解题代码

代码实现

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 刷题时

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/122326.html

剑指offer系列——剑指 Offer 18. 删除链表的节点（C语言）

摘要：导航小助手剑指删除链表的节点题目详情解题思路源代码总结剑指删除链表的节点题目详情给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。 ...

Jokcy 2021-09-08 09:36 评论0 收藏0
剑指offer系列——剑指 Offer 22. 链表中倒数第k个节点（C语言）

摘要：导航小助手剑指链表中倒数第个节点题目详情解题思路源代码总结剑指链表中倒数第个节点题目详情输入一个链表，输出该链表中倒数第个节点。为了符合大多数人的习惯，本题从开始计数，即链表的尾节点是倒数第个节点。这个链表的倒数第个节点是值为的节点。 ...

voidking 2021-09-14 17:57 评论0 收藏0
剑指offer系列——剑指 Offer 06. 从尾到头打印链表（C语言）

摘要：导航小助手剑指从尾到头打印链表题目详情解题思路源代码总结剑指从尾到头打印链表题目详情输入一个链表的头节点，从尾到头反过来返回每个节点的值用数组返回。时间复杂度方法先反转链表并求长度，在将反转后的链表数据拷贝至数组中。 ...

DevTTL 2021-09-04 16:41 评论0 收藏0
剑指offer系列——剑指 Offer 24. 反转链表（C语言）

摘要：假设反转对象节点为，反转指向的结点为，反转后指向的结点为首结点。当然也可以根据栈先进后出的特点，使用栈反转链表。 ⭐️前面的话⭐️ 大家好！博主开辟了一个新的专栏—...

weakish 2021-09-03 10:29 评论0 收藏0
JavaSE与数据结构基础知识系列——专栏导航

⭐️前面的话⭐️ 大家好！这是Java基础知识与数据结构博文的导航帖，收藏我！学习Java不迷路！ ?博客主页：未见花闻的博客主页 ?欢迎关注?点赞?收藏⭐️留言? ?本文由未见花闻原创，CSDN首发！ ?首发时间：?2021年11月11日? ✉️坚持和努力一定能换来诗与远方！ ?参考书籍：?《Java核心技术卷1》，?《Java核心技术卷2》，?《Java编程思想》 ?参考在线编程网站：?牛...

Cc_2011 2021-11-12 10:36 评论0 收藏0