Loading... 很巧妙的一道算法题。答案很简单，但是这个方法… 妙啊！ 原文链接：[小吴师兄的文章](https://cxyxiaowu.com/articles/2019/04/04/1554345488302.html) ##题目 <button class=" btn m-b-xs btn-primary btn-addon" onclick="window.open('https://leetcode-cn.com/problems/single-number/','_blank')"><i class="glyphicon glyphicon-hand-right"></i>原题戳我！</button> ###描述 > 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 !> 说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ ###示例 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异或的真值表： | A | B | ^ | | ------------ | ------------ | ------------ | | T | T | F | | T | F | T | | F | T | T | | F | F | F | 根据这个真值表可以发现，相同的数异或得到的结果一定是0，而0和任何数异或都等于它本身。所以我们可以通过异或所有数来找出答案。 ##问题进阶 ###描述 有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。 ###示例 : 输入: [1,2,2,1,3,4] 输出: [3,4] ##进阶题解析 根据前面找一个不同数的思路算法，在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果。 然后，因为这两个只出现一次的元素一定是不相同的，所以这两个元素的二进制形式肯定至少有某一位是不同的，即一个为 0 ，另一个为 1 ，现在需要找到这一位。 根据异或的性质 任何一个数字异或它自己都等于 0，得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。 再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。 - 将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个 - 将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。 i> 这里分成两部分，就是把两个单独的数分在了两个组里面。这时再安照之前的解法即可解出。 这样就解出题目。忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。 最后再说一下，位运算真是个神奇的东西。 最后修改：2019 年 04 月 11 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏