樊梓慕：个人主页
个人专栏：《C语言》《数据结构》《蓝桥杯试题》
每一个不曾起舞的日子，都是对生命的辜负。
目录
前言：
一只单身狗：
两只单身狗：
前言：
本篇主要讲解LeetCode上的经典题型：只出现一次的数字，我汇总了该类问题的两种情况（一只单身狗、两只单身狗）并进行分析讲解和代码实现，学习完本篇文章你会掌握一种全新的思路：异或法，希望大家多多支持博主创作，博主会持续带来更多优质内容
=========================================================================
GITEE相关代码：fanfei_c的仓库
=========================================================================
一只单身狗：
LeetCode原题链接：只出现一次的数字
题目：给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
传统方法我们可以想到利用计数器，但这种算法效率不理想。
今天我们就来学习异或法。
首先我们来复习一下位操作符：
&：两个数字对应二进制位有0则为0，两个同时为1才是1。
|：两个数字对应二进制位有1则为1，两个同时为0才是0。
^：两个数字对应二进制位相同为0，相异为1。
想要具体了解位操作符的同学可以移步这里位操作符的应用，他会帮助你对本篇内容的理解更加透彻。
我们知道两个相同的数字异或得到的结果为0，而0^某个数字就是它本身，且异或操作符满足交换律。
那么既然给定的该数组nums满足只有其中一个元素出现一次，其他数字都出现两次的情况，我们就可以利用^的特性来梳理逻辑：将nums数组的内容异或到一起，此时相同的数字就都异或为0了，剩余一个单独的数字与0异或得到它本身。
代码实现：
int find_single_dog1(int arr[], int sz)
{
int i = 0;
int ret = 0;
for (i = 0; i < sz; i++)
{
ret ^= arr[i];
}
return ret;
}
int main()
{
int arr[] = { 1,2,3,4,7,1,2,3,4 };
int sz = sizeof(arr) / sizeof(arr[0]);
int dog = find_single_dog1(arr, sz);
printf("%d\n", dog);
return 0;
}
两只单身狗：
LeetCode原题链接：只出现一次的数字(2)
题目：给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
假设仍然按照异或法的逻辑能不能实现呢？
其实我们只需要将两只单身狗的问题转化为一只单身狗就好了，需要做的就是将两只单身狗分开处理，这样就到了我们熟悉的领域了。
那么我们如何才能将两只单身狗分开呢？
我们假设数组为：1，2，3，4，5，1，2，3，4，6。
观察如果将该数组异或到一起得到：5^6。
根据异或的特性我们知道两个不相同的二进制数字异或的结果为1，那么我们可不可以根据这一特性来区分两个单身狗呢，我们可以利用数组异或的结果取一个位为1的位，在该位上，与5相同的分为一组，与6相同的分为一组。
比如：
分完组后是不是很熟悉，没错就是一只单身狗的处理方法了。
代码实现：
void find_single_dog2(int arr[], int sz, int* pd1, int* pd2)
{
//1. 所有数字异或在一起
int ret = 0;//5 ^ 6
int i = 0;
for (i = 0; i < sz; i++)
{
ret ^= arr[i];
}
//2. 计算ret的第几位是1
int pos = 0;
for (i = 0; i < 32; i++)
{
if (((ret >> i) & 1) == 1)
{
pos = i;
break;
}
}
//计算数组中元素的第pos为1的异或
for (i = 0; i < sz; i++)
{
if (((arr[i] >> pos) & 1) == 1)
{
*pd1 ^= arr[i];
}
}
//计算数组中元素的第pos为0的异或
*pd2 = ret ^ *pd1;
}
int main()
{
int arr[] = { 1,2,3,4,5,1,2,3,4,8 };
int dog1 = 0;
int dog2 = 0;
int sz = sizeof(arr) / sizeof(arr[0]);
find_single_dog2(arr, sz, &dog1, &dog2);//dog1、dog2为返回型参数
printf("%d %d", dog1, dog2);
return 0;
}
单身狗问题是笔试非常高频的题型，掌握了这种方法相信会使你的解题思路更加清晰，如果本篇文章对你有帮助，希望多多支持博主，博主会持续创作优质内容
相关文章
您阅读本篇文章共花了：
发表评论