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

.

📝Gitee主页：倔强的石头的gitee主页

⏩ 文章专栏：《C++指南》

期待您的关注

文章目录

• 引言
• • 一、只出现一次的数字（一）简单
  • • 题目描述
    • 解题思路
    • 代码实现及解释
    • 二、只出现一次的数字 （二）中等
    • • 题目描述
      • 解题思路
      • 代码实现及解释
      • 三、只出现一次的数字 （三）困难
      • • 题目描述
        • 解题思路
        • 代码实现及解释
        • 解题总结
        • • 共性
          • 差异

            引言

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

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

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

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

            【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& 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& nums) {
                        int res = 0;
                        // 循环遍历每一位二进制位，从第0位到第31位
                        for (int i = 0; i > i) & 1); 
                            }
                            // 如果这一位上1出现的次数对3取余为1，将它加到结果res对应的二进制位上
                            res += (sum % 3) > i) & 1); ：将 num 右移 i 位，使得当前要统计的二进制位移到最低位，然后与 1 进行逻辑与操作。如果该位为 1，结果为 1；如果该位为 0，结果为 0。将这个结果累加到 sum 中，实现对当前位上 1 出现次数的统计。

              • res += (sum % 3) int ret = 0; // 遍历数组，将所有元素异或，得到两个只出现一次元素的异或结果 for (auto i : nums) { ret ^= i; } int rightone = 0; // 从右往左找到异或结果中第一个为1的位 for (int i = 0; i i) & 1) == 1) { rightone = 1 if (i & rightone) { num1 ^= i; } else { num2 ^= i; } } return {num1, num2}; } ulliint ret = 0; ：初始化变量 ret 为 0，用于存储数组所有元素异或的结果。/lilifor (auto i : nums) ：遍历数组 nums 中的每一个元素 i，将 ret 与 i 进行异或操作，最终 ret 是两个只出现一次元素的异或结果。/liliint rightone = 0; ：初始化变量 rightone 为 0，用于存储从右往左找到的异或结果中第一个为 1 的位。/lilifor (int i = 0; i > i) & 1) == 1) ：将 ret 右移 i 位，判断当前位是否为 1 。如果是 1 ，则执行以下操作。
              • rightone = 1