【C++指南】“单身狗问题”——只出现一次的数字 系列问题
.💓 博客主页：倔强的石头的ZEEKLOG主页
📝Gitee主页：倔强的石头的gitee主页
⏩ 文章专栏：《C++指南》
期待您的关注
文章目录
- 引言
- 一、只出现一次的数字（一）简单
- 题目描述
- 解题思路
- 代码实现及解释
- 二、只出现一次的数字 （二）中等
- 题目描述
- 解题思路
- 代码实现及解释
- 三、只出现一次的数字 （三）困难
- 题目描述
- 解题思路
- 代码实现及解释
- 解题总结
- 共性
- 差异
- 一、只出现一次的数字（一）简单
引言
在算法领域，“只出现一次的数字”系列题目是经典的位运算应用题型，这类问题又被形象的称为“单身狗问题”。
这一系列题目通过不同的数字出现次数设定，考查我们对位运算特性的理解和运用能力。
下面我们将对三道相关题目进行深入剖析。
位运算知识可阅读配套文章：
【C++指南】位运算知识详解
一、只出现一次的数字（一）简单
题目描述
给定一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。要求找出那个只出现了一次的元素，并且必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
解题思路
本题的关键在于利用位运算中的异或运算（^）特性。异或运算具有以下性质：
- 一个数与自身异或结果为
0，例如a ^ a = 0。 - 任何数与
0异或结果为其本身，例如a ^ 0 = a。 - 异或运算满足交换律和结合律，即
a ^ b = b ^ a，(a ^ b) ^ c = a ^ (b ^ c)。
基于这些性质，我们可以将数组中所有数字依次进行异或操作。由于出现两次的数字会相互抵消（异或为 0 ），最终得到的结果就是只出现一次的那个数字。
代码实现及解释
classSolution{public:intsingleNumber(vector<int>& nums){int ret =0;// 遍历数组中的每一个元素for(auto i : nums){// 将ret与当前元素i进行异或操作 ret ^= i;}return ret;}};int ret = 0;：初始化一个变量ret并赋值为0，用于存储最终的异或结果。for (auto i : nums)：这是 C++ 11 引入的范围for循环，用于遍历数组nums中的每一个元素，将当前元素依次赋值给i。ret ^= i;：等价于ret = ret ^ i，将ret与当前元素i进行异或操作。在遍历过程中，出现两次的元素会相互抵消（异或为0），最终ret就会是只出现一次的那个数字。
二、只出现一次的数字 （二）中等
题目描述
给定一个整数数组 nums，除某个元素仅出现一次外，其余每个元素都恰出现三次。需要找出并返回那个只出现了一次的元素，并且必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
解题思路
对于本题，我们采用位运算的思路，考虑整数的 32 个二进制位。因为除目标数字外其他数字都出现三次，所以我们可以对数组中所有数的每一位二进制位进行统计·
具体来说，对于每一位二进制位，统计数组中所有元素在该位上 1 出现的次数。
由于其他数字都出现三次，那么该位上 1 出现的次数对 3 取余的结果，就是目标数字在该位上的值。(如果出现3次，取模为0；只出现一次，取模为1)
通过对 32 位二进制位都进行这样的操作，我们就能还原出只出现一次的那个数字。
代码实现及解释
classSolution{public:intsingleNumber(vector<int>& nums){int res =0;// 循环遍历每一位二进制位，从第0位到第31位for(int i =0; i <32;++i){int sum =0;// 遍历数组中的每一个元素for(auto num : nums){// 右移i位，再与1逻辑与，统计当前位上1出现的次数 sum +=((num >> i)&1);}// 如果这一位上1出现的次数对3取余为1，将它加到结果res对应的二进制位上 res +=(sum %3)<< i;}return res;}};int res = 0;：初始化结果变量res，用于存储最终找到的只出现一次的数字。for (int i = 0; i < 32; ++i)：外层循环用于遍历整数的 32 个二进制位，从第0位到第31位。int sum = 0;：在每次遍历新的二进制位时，初始化sum为0，用于统计当前位上1出现的次数。for (auto num : nums)：内层循环遍历数组nums中的每一个元素num。sum += ((num >> i) & 1);：将num右移i位，使得当前要统计的二进制位移到最低位，然后与1进行逻辑与操作。如果该位为1，结果为1；如果该位为0，结果为0。将这个结果累加到sum中，实现对当前位上1出现次数的统计。res += (sum % 3) << i;：对sum对3取余，如果结果为1，说明目标数字在当前二进制位上是1，将1左移i位后加到res中，实现对结果数字对应二进制位的设置。
三、只出现一次的数字 （三）困难
题目描述
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。需要找出只出现一次的那两个元素，可以按任意顺序返回答案，并且必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
解题思路
本题的解题思路基于异或运算和分组的思想。
- 首先，将数组中所有元素进行异或操作。根据异或运算的性质，出现两次的元素会相互抵消（异或为
0），最终得到的结果是两个只出现一次元素的异或值。 - 然后，找到这个异或值中从右往左第一个为
1的位。因为这两个只出现一次的元素在该位上的值不同（异或结果为1说明两个操作数该位不同），所以可以根据这一位是1还是0将原数组分成两组。 - 最后，分别对这两组元素进行异或操作。
由于分组后每组中除了目标元素外其他元素都出现两次，所以每组异或的结果就是对应的那个只出现一次的元素。
代码实现及解释
vector<int>singleNumber(vector<int>& nums){int ret =0;// 遍历数组，将所有元素异或，得到两个只出现一次元素的异或结果for(auto i : nums){ ret ^= i;}int rightone =0;// 从右往左找到异或结果中第一个为1的位for(int i =0; i <32;++i){if(((ret >> i)&1)==1){ rightone =1<< i;break;}}int num1 =0;int num2 =0;// 根据找到的位将数组元素分组并分别异或for(auto i : nums){if(i & rightone){ num1 ^= i;}else{ num2 ^= i;}}return{num1, num2};}int ret = 0;：初始化变量ret为0，用于存储数组所有元素异或的结果。for (auto i : nums)：遍历数组nums中的每一个元素i，将ret与i进行异或操作，最终ret是两个只出现一次元素的异或结果。int rightone = 0;：初始化变量rightone为0，用于存储从右往左找到的异或结果中第一个为1的位。for (int i = 0; i < 32; ++i)：循环遍历 32 个二进制位，寻找第一个为1的位。if (((ret >> i) & 1) == 1)：将ret右移i位，判断当前位是否为1。如果是1，则执行以下操作。rightone = 1 << i;：将1左移i位，得到表示该位为1的掩码。break;：找到第一个为1的位后，跳出循环。int num1 = 0; int num2 = 0;：初始化两个变量num1和num2，用于分别存储两组异或的结果。for (auto i : nums)：再次遍历数组nums中的每一个元素i。if (i & rightone)：判断元素i在找到的位上是否为1。如果是1，则将i与num1进行异或操作；否则，将i与num2进行异或操作。return {num1, num2};：返回包含两个只出现一次元素的数组。
解题总结
“只出现一次的数字”系列题目围绕着在不同数字出现次数规则下找出特殊数字展开，主要通过位运算来解决。
共性
- 位运算的运用：充分利用异或运算的特性，异或运算在处理出现次数有规律（如出现两次、三次）的场景中起到关键作用。对于出现两次的数字，异或可使其相互抵消；对于更复杂的出现次数情况，通过对二进制位的统计和分组来处理。
- 空间和时间复杂度要求：都要求线性时间复杂度（通常是一次遍历数组）和常量级额外空间，这就限制了不能使用额外的数据结构来存储中间结果，必须在位运算的思路上进行巧妙设计。
差异
- 题目 一：数字出现情况相对简单，除一个数字外其他都出现两次，直接利用异或运算依次对数组元素操作即可得到结果。
- 题目 二：由于多数数字出现三次，不能简单用异或抵消，而是通过对每一位二进制位上
1出现次数统计并对3取余来确定目标数字每一位的值。 - 题目 三：存在两个只出现一次的数字，先通过整体异或得到两个目标数字的异或结果，再找到异或结果中特定的位进行分组，分别异或得到两个目标数字。
解决这类题目时，关键是深入理解位运算的特性，根据数字出现次数的特点，合理设计对二进制位的操作方式，通过统计、分组等手段实现高效的算法。
本文完
关于位运算知识可阅读配套文章：
【C++指南】位运算知识详解
