漫画：位运算系列篇（只出现一次的数字）

01 PART

Single Number

这道题，大家先想一想是用什么思路进行求解？

第136题：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

PS：建议大家停留个两分钟先想一想...直接拉下去看题解就没什么意思了。

02 PART

题目分析

位运算的题目我们已经讲了好几道了，这道也不例外，也是其中一个非常典型的例子！属于必须掌握的题型。

直接分析，我们要找只出现一次的数字，并且已知了其他的数字都只出现了两次。那么这种一听其实就应该想到需使用位运算来进行求解。最好的，就是在读完题目的瞬间，直接条件反射！（当然，如果你现在第一反应是想到 通过遍历统计，或者其他如使用hashmap 等方式来进行求解，那我觉得你的位运算这块，是有必要加强练习力度的。如果你第一反应，连思路都没有，那我觉得对于整个算法的能力这块，都是比较欠缺的，需要下苦功！）

回到题目，如何使用位运算进行求解呢？对于任意两个数a和b，我们对其使用 “异或”操作，应该有以下性质：

• 任意一个数和0异或仍然为自己： a⊕0=a
• 任意一个数和自己异或是0： a⊕a=0
• 异或操作满足交换律和结合律：

a⊕b⊕a=(a⊕a)⊕b=0⊕b=b

可能有人直接都不知道异或是什么，所以还是举个例子，比如5异或3，也就是5⊕3，也就是5^3，是下面这样：

根据分析，得出代码：（c++版本）

//CPP
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }
        return ans;
    }
};

（java版本）

//JAVA
class Solution {
    public int singleNumber(int[] nums) {
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            ans = ans ^ nums[i];
        }
        return ans;
    }
}

(python版本)

//py
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums)):
            ans ^= nums[i]
        return ans

郑重申明（读我的文章必看）：

• 本系列所有教程都不会用到复杂的语言特性，不需要担心没有学过相关语法，使用各语言纯属本人爱好。
• 作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode上进行过测试运行。
• 算法思想才是最重要的。

03 PART

题目进阶

如果修改上面的题目，除了某个元素只出现一次，其余元素都出现了3次以上，那么该如何求解？

修改一个条件之后，本题的难度大幅度提升！“异或”的方式看起来似乎没办法运用在“其余数出现3次以上”的条件中。那对于这种问题又该如何求解？我这里给出几种思路，大家下去分析一下，明天我会公布这道衍化题型的解决方案：

• 思路1：使用hashmap，统计每个数字出现的次数，最后返回次数为1的数字。。。然后等待一段时间，接到很遗憾的通知。
• 思路2：上面的题目，对于相同的两个数，进行异或运算，我们可以进行“抵消”，那是否可以找到一种方式，来让相同的三个数进行相互抵消呢？
• 思路3：是不是可以通过数学的方式来进行计算？