欢迎关注天善智能，我们是专注于商业智能BI，人工智能AI，大数据分析与挖掘领域的垂直社区，学习，问答、求职一站式搞定！
对商业智能BI、大数据分析挖掘、机器学习，python，R等数据领域感兴趣的同学加微信：tstoutiao，邀请你进入数据爱好者交流群，数据爱好者们都在这儿。
作者： 程序员小吴
个人公众号：五分钟学算法
总第62篇/程序员小吴
这是一道看完答案会觉得很简单，但做之前很难想到答案的题目！！！
不信？
Let us go ！
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
查看答案之前，不妨独立思考一下，看看能不能想出解决方案：）
题目解析
根据题目描述，由于加上了时间复杂度必须是O(n)，并且空间复杂度为O(1)的条件，因此不能用排序方法，也不能使用map数据结构。
小吴想了一下午没想出来，答案是使用 位操作Bit Operation 来解此题。
将所有元素做异或运算，即a[1] ⊕ a[2] ⊕ a[3] ⊕ …⊕ a[n]，所得的结果就是那个只出现一次的数字，时间复杂度为O(n)。
异或
异或运算A ⊕ B的真值表如下：
AB⊕FFFFTTTFTTTF
动画演示
进阶版
有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。
示例 :
输入: [1,2,2,1,3,4]
输出: [3,4]
题目再解析
根据前面找一个不同数的思路算法，在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果。
然后，因为这两个只出现一次的元素一定是不相同的，所以这两个元素的二进制形式肯定至少有某一位是不同的，即一个为 0 ，另一个为 1 ，现在需要找到这一位。
根据异或的性质 任何一个数字异或它自己都等于 0，得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。
再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。
将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个
将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。
这样就解出题目。忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。
动画再演示
End
本题的基础版来源于 LeetCode 第 136 号问题：只出现一次的数字。虽然题目难度是 简单，但解法真的很巧妙。感兴趣的同学可以根据思路去回答一下：https://leetcode-cn.com/problems/single-number/
Python的爱好者社区历史文章大合集：
2018年Python爱好者社区历史文章合集（作者篇）
2018年Python爱好者社区历史文章合集（类型篇）
关注后在公众号内回复“ 课程 ”即可获取：
小编的转行入职数据科学（数据分析挖掘/机器学习方向）【最新免费】
小编的Python的入门免费视频课程！
小编的Python的快速上手matplotlib可视化库！
崔老师爬虫实战案例免费学习视频。
陈老师数据分析报告扩展制作免费学习视频。
玩转大数据分析！Spark2.X + Python精华实战课程免费学习视频。
网友评论