【C++指南】“单身狗问题”——只出现一次的数字 系列问题

@TOC

引言

在算法领域，“只出现一次的数字”系列题目是经典的位运算应用题型，这类问题又被形象的称为“单身狗问题”。

这一系列题目通过不同的数字出现次数设定，考查我们对位运算特性的理解和运用能力。

下面我们将对三道相关题目进行深入剖析。

**位运算知识可阅读配套文章：

【C++指南】位运算知识详解**

一、只出现一次的数字（一）简单

题目描述

给定一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。要求找出那个只出现了一次的元素，并且必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

解题思路

本题的关键在于利用位运算中的异或运算（^）特性。异或运算具有以下性质：

• 一个数与自身异或结果为 0，例如 a ^ a = 0。
• 任何数与 0 异或结果为其本身，例如 a ^ 0 = a。
• 异或运算满足交换律和结合律，即 a ^ b = b ^ a ，(a ^ b) ^ c = a ^ (b ^ c) 。

基于这些性质，我们可以将数组中所有数字依次进行异或操作。由于出现两次的数字会相互抵消（异或为 0 ），最终得到的结果就是只出现一次的那个数字。

代码实现及解释

class Solution {
public:
    int singleNumber(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 位二进制位都进行这样的操作，我们就能还原出只出现一次的那个数字。

代码实现及解释

class Solution {
public:
    int singleNumber(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，其中恰好有两个元素只出现一次，其余所有元素均出现两次。需要找出只出现一次的那两个元素，可以按任意顺序返回答案，并且必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

解题思路

本题的解题思路基于异或运算和分组的思想。

1. 首先，将数组中所有元素进行异或操作。根据异或运算的性质，出现两次的元素会相互抵消（异或为 0 ），最终得到的结果是两个只出现一次元素的异或值。
2. 然后，找到这个异或值中从右往左第一个为 1 的位。因为这两个只出现一次的元素在该位上的值不同（异或结果为 1 说明两个操作数该位不同），所以可以根据这一位是 1 还是 0 将原数组分成两组。
3. 最后，分别对这两组元素进行异或操作。由于分组后每组中除了目标元素外其他元素都出现两次，所以每组异或的结果就是对应的那个只出现一次的元素。

代码实现及解释

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++指南】位运算知识详解**