19 . 只出现一次的数字

题目介绍

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

提示：

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

class Solution { public: int singleNumber(vector<int>& nums) { } };

全文1300字，阅读+思考 8min

原题链接：136. 只出现一次的数字 - 力扣（LeetCode）

解析

1 . 本题需求很简单，即给你一个数组(vector<int>) ，找出数组中只出现一次的数字并返回

且其余数字都出现了两次

哈希

1 . 对于要找出单身狗数字，很容易想到的思路：遍历数组一遍，统计每个数字出现的次数

2 . 只需要统计一遍，就能知道每个数字出现多少遍。

代码初步构建：

class Solution { public: int singleNumber(vector<int>& nums) { map<int,int> mp;// 数字 ，出现的次数 for(auto e:nums) { mp[e]++; } //统计完毕 } };

3 . 已经统计好每个数字出现的次数，那么再遍历一遍数组

4 . 一旦遇到次数为1（即mp[e] == 1)就立刻返回e

class Solution { public: int singleNumber(vector<int>& nums) { map<int,int> mp;// 数字 ，出现的次数 for(auto e:nums) { mp[e]++; } for(auto e:nums) { if(mp[e] == 1) return e; } return 0;//为了编译通过，需要再加一个return } };

注：

1 . 这个方法逻辑和写法没有问题

2 . 可使用了O(n)的空间开销而非常量，但时间开销符合要求O(n)

异或

此方法重点掌握——

1 . 回忆：异或。全称：按位异或——二进制位运算之一

2 . 异或的本质 ： 模二乘法运算

a . 0 ^ 0 = 0 0 ^ 1 = 1 1^1 = 0

b . a ^ 0 = a a ^ a = 0;

3 . 我们正是利用”b中式子”完成需求

a . 当给出的数组都是成双成对的数字，那么可想而知：将所有数字进行异或结果为0

b , 异或运算与顺序无关，它只与参与运算的位有关

c . 当数组中出现唯一一个单身狗数字，那么 0 ^ singleDog == singleDog

d. 所以：这个singleDog就是将所有数组异或之后的结果

代码呼之欲出：

class Solution { public: int singleNumber(vector<int>& nums) { int sigledog = 0;// 设置单身狗的初始值为0，因为0和任何数异或都保持为该数 for(auto& e:nums) { sigledog ^= e; } return sigledog; } };

总结以及完整参考代码

class Solution { public: int singleNumber(vector<int>& nums) { map<int,int> mp;// 数字 ，出现的次数 for(auto e:nums) { mp[e]++; } for(auto e:nums) { if(mp[e] == 1) return e; } } };

class Solution { public: int singleNumber(vector<int>& nums) { int sigledog = 0;// 设置单身狗的初始值为0，因为0和任何数异或都保持为该数 for(auto& e:nums) { sigledog ^= e; } return sigledog; } };

本周其他算法一见：

15 . 有效的括号-CSDN博客

16 . 买卖股票的最佳时机-CSDN博客

17 . 爬楼梯-CSDN博客

18 . 杨辉三角-CSDN博客

20 . 多数元素-CSDN博客

赶快动起手来吧