文章目录

• 前言
• 题1 - 消失的数字
• 题2 - 数组中数字出现的次数

前言

本章记录着我本猩猩美好的刷题日常，希望在我的解析下可以有和家凤老师一样的自信，这些题我一拿到手就会。

题1 - 消失的数字

仙人指路➡️： 消失的数字

🔍分析：
题目中明确数组是包含从 0 到 n 的所有整数，但却缺少一个。
咱们可以这么想：数组是从 0 到 n 的所有整数，是个连续的、升序的数组，那消失的数字就可以用 从 0 到 n 的完整数组元素之和 减去 题目所给的数组元素之和（缺一个数字的）

所以有🔱方法一：完整数组之和 - 所给数组之和
具体代码：

int missingNumber(int* nums, int numsSize){     int sum1 = 0;     int sum2 = 0;     for(int i = 0;i < numsSize + 1;i++)     {  sum1 += i;     }     for(int i = 0;i < numsSize;i++)     {  sum2 += nums[i];     }     return sum1 - sum2;//完整数组之和 - 所给数组之和}

另外，还有一种蛋黄派看了都直称“妙啊”的方法：异或 （在操作符章节已学习）
复习 异或 的性质：

• 任何值和0异或等于其本身，即：A ^ 0 = A
• 异或本身等于0，即 A ^ A = 0
• 异或满足结合律，即 A ^ B ^ C = A ^ ( B ^ C)

🔱方法二： 利用 异或 的性质，创建一个变量 miss（miss=0） ，根据miss = miss ^ x ^ x，先对0 ~ n完整数序异或，再对所给数组异或，重复出现的数字异或为0，则miss为出现一次的数字，也就是数组中缺失的数字。
结合图解：

具体代码：

int missingNumber(int* nums, int numsSize){    int miss = 0;    for (int i = 0; i < numsSize + 1; i++)//注意该处是完整的0~n,是numSize+1    { miss ^= i;    }    for (int i = 0; i < numsSize; i++)    { miss ^= nums[i];    }    return miss;}

题2 - 数组中数字出现的次数

仙人指路➡️： 数组中数字出现的次数

🔍分析：
❓先将问题简单化，当数组nums里除一个数字之外，其他数字都出现了两次，找出该数字。
有了题1的经验，我们直接妙啊解法： 异或

int singleNumber(int* nums, int numsSize){int res = 0;for (int i = 0; i < numsSize; i++){res ^= nums[i];}return res;}

重复出现的数字异或为0，剩下的就是出现一次的数字（单身狗🐕）

回到这题：一个数组nums里除两个数字之外，其他数字都出现了两次，找出这两个数字。（设这两个数字分别为num1，num2）

如果直接求该数组异或和，会得到一个看似没意义的结果。

对[2,3,2,3,4,6]异或,结果是4^6

解决思路： 将原数组分为两个子数组，让这两个出现一次的数字（单身狗）分别分到两个数组中，这便变成了找一个单身狗的解法了。
❓如何拆分原数组？

4 ^ 6 的二进制为010 。由异或：相同为0，相异为1可以知道，为1的二进制位说明4 和 6在该位上不相等，即一定是一个为0一个为1 。这正是我们拆分数组的关键。

图解：

分组：

1. 找出两个单身狗的异或和结果
2. 找出用于区分单身狗的二进制位（称为特殊位）
3. 根据特殊位来拆分，并找出单身狗

具体代码：

int* singleNumbers(int* nums, int numsSize, int* returnSize){    //[2,3,2,3,4,6] ==> [4,6]    int ret = 0;    for(int i = 0;i < numsSize;i++)    { ret ^= nums[i];//两个单身狗异或的结果  4^6 = 010    }    int mask = 1;//0000 0001    while((ret & mask) == 0)//找用于区分单身狗的位    { mask <<= 1;    }    int num1 = 0;    int num2 = 0;    for(int i = 0;i < numsSize;i++)    { if((mask & nums[i]) == 0)//特殊位 拆分两个单身狗 {     num1 ^= nums[i]; } else {     num2 ^=nums[i]; }    }    int* arr = (int*)malloc(2 * sizeof(int));    *returnSize = 2;    arr[0] = num1;    arr[1] = num2;    return arr;}

恳请各位铁汁们点赞收藏评论加关注，你们的支持是我坚持的动力~