本文共 2633 字，大约阅读时间需要 8 分钟。
目录
Ⅰ 题目描述：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1：输入: [2,2,1] 输出: 1
示例 2：输入: [4,1,2,1,2] 输出: 4❗解题思路❗：
刚看到这道题时，想起来之前有看过一个类似的知识点 → ，于是?
class Solution {public: int singleNumber(vector & nums) { // 0^x = x int singleNumber = 0; for (int i = 0; i < nums.size(); ++i) { singleNumber = singleNumber^nums[i]; } return singleNumber; }}; 这样算法复杂度O(n)，也不占用额外空间，测试通过，发现时间似乎还可以更快~
❗评论&题解❗：
? 1、数学方法： 2 ∗ (a + b + c) − ( a + a + b + b + c ) = c
这是用 Python 才能完成的，因为 Python 中有 se t集合，set 集合中的元素不可重复，利用这个属性刚好可以完成这个问题。
class Solution: # 注意 Python 和 Python3 区别还挺大的, 下面是 Python3代码 …… def singleNumber(self, nums: List[int]) -> int: return sum(set(nums))*2 - sum(nums)
然而这种方法比异或要慢多了，内存消耗也大一些 ……
? 2、哈希表
遍历 nums 中的每一个元素；查找哈希表中是否有当前元素的键；如果没有，将当前元素作为键插入哈希表；如果有，删除掉；最后，hash_table 中仅有一个元素，获取它。
class Solution {public: int singleNumber(vector & nums) { // map同时拥有实值(value)和键值(key),set元素的键值就是实值，实值就是键值, set不允许两个元素有相同的键值。 set s; for (int i = 0; i < nums.size(); ++i) { // 在容器中搜索与等效元素，如果找到则返回一个迭代器，否则返回一个set :: end的迭代器 if (s.find(nums[i]) == s.end()) { s.insert(nums[i]); } else { s.erase(nums[i]); } } return *(s.begin()); }}; 
Ⅱ 题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1：输入: [2,2,3,2] 输出: 3
示例 2：输入: [0,1,0,1,0,1,99] 输出: 99❗解题思路❗：
参考上题中的数学解法，使用 Python 中的 set 。emmm，set 使用了O(n)额外空间，其实并没有达到题目中的要求 ?
class Solution: def singleNumber(self, nums: List[int]) -> int: return int((3*sum(set(nums)) - sum(nums)) / 2)
❗评论&题解❗：
? 1、位运算（这种方法可以推广至 除一个数字出现一次外，其余数字都出现 k 次）：将所有出现的数字转换为二进制。假如第 0 位 1 的个数是 k 的倍数，那么要求的这个数在该位一定是 0，若不是 k 的倍数，那么要求的这个数在该位一定是 1，第 1 位的 1 一直到第 31 位的 1 的个数同理。很巧妙的方法！
class Solution {public: int singleNumber(vector & nums) { int ans = 0; // 考虑每一位 for (int i = 0; i < 32; ++i) { int count = 0; //考虑每一个数 for (int j = 0; j < nums.size(); ++j) { // 当前位是否是 1 if ((nums[j] >> i & 1) == 1) { count += 1; } } // 1 的个数是否是 3 的倍数 if (count % 3 != 0) { ans = ans | (1 << i); } } return ans; }}; 
? 2、数字电路设计思想，我们是否能够定义一种运算（代替异或），使得三个数运算的结果为 0 呢 ？
通过定义某种运算 #，使得 0 # 1 = 1，1 # 1 # 1 = 0。
转载地址：http://ostai.baihongyu.com/