写在前面咱不是计算机专业的，却一直对计算机算法感兴趣，也一直致力于减小自己程序的复杂度[捂脸]，昨日吃饭时，某老铁考我一道算法题，思索良久，辗转反侧，夜不能寐，遂厚着脸皮去问答案，然则令吾汗颜，果真是一波骚操作……看题！给定一个非空整数数组, 除了某个元素只出现一次以外, 其余每个元素均出现两次, 找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？示例 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 的真值表如下:ABA ⊕ BFalseFalseFalseTrueTrueTrueTrueFalseTrueFalseTrueTrue即:不相等即为True题目进阶有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。示例 :输入: [1,2,2,1,3,4] 输出: [3,4]题目再解析根据前面找 一个 不同数的思路算法，在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果, 为了叙述方便, 我们这里把这个结果简单记为字母 K 。因为这两个只出现一次的元素一定是不相同的，所以 K 一定不为零, 将K从左往右数的第一个为1的位记录下来。再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。这样就解出题目, 忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。举个例子吧假如:输入是: [1,2,2,1,3,4,7,7] 进行异或操作:>>> 1^2^2^1^3^4 # python的异或操作符7异或完毕为7即0000 0111数字7从左往右数的第一个为1的位为0000 0111 ^也就是第六位以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分(也就是数组大于等于4的分一组, 小于4的分一组)即[4, 7, 7] 和 [1,2,2,1,3]>>> # 数组[4,7,7]所有元素做异或操作>>> 4^7^74>>> 数组[1,2,2,1,3]所有元素做异或操作>>> 1^2^2^1^33大功告成！！据说此题来源于 LeetCode 第 136 号问题：https://leetcode-cn.com/probl…