一道让你拍案叫绝的算法题

淩亂°似流年 2023-06-13 09:10 28阅读 0赞

这是一道看完答案会觉得很简单，但做之前很难想到答案的题目！！！

不信？

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的真值表如下：

| A | B | ⊕ | |:------------- |:---------------:| -------------:| | F | F | F | | F | T | T | | T | F | T | | T | T | F |

## 动画演示 ##

![v2-4ea1cce62d1d671463f4e2c66c8d0dbb\_b.gif][v2-4ea1cce62d1d671463f4e2c66c8d0dbb_b.gif]

## 进阶版 ##

有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。

## 示例 : ##

输入: \[1,2,2,1,3,4\]  
输出: \[3,4\]

## 题目再解析 ##

根据前面找一个不同数的思路算法，在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果。

然后，因为这两个只出现一次的元素一定是不相同的，所以这两个元素的二进制形式肯定至少有某一位是不同的，即一个为 0 ，另一个为 1 ，现在需要找到这一位。

根据异或的性质 `任何一个数字异或它自己都等于 0`，得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。

再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。

*  将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个  
    
 *  将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。

这样就解出题目。忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。

## 动画再演示 ##

![v2-8b6da8db75ef5a017c03af5fc6d0bd38\_b.gif][v2-8b6da8db75ef5a017c03af5fc6d0bd38_b.gif]

## End ##

本题的基础版来源于 LeetCode 第 136 号问题：只出现一次的数字。虽然题目难度是 简单，但解法真的很巧妙。感兴趣的同学可以根据思路去回答一下：[https://leetcode-cn.com/problems/single-number/][https_leetcode-cn.com_problems_single-number] 。

[v2-4ea1cce62d1d671463f4e2c66c8d0dbb_b.gif]: https://img-blog.csdnimg.cn/img_convert/3a3443f37a0a1c719d8556e2b02524da.gif
[v2-8b6da8db75ef5a017c03af5fc6d0bd38_b.gif]: https://img-blog.csdnimg.cn/img_convert/e7d4093306945bd53f723e42a40bc0d9.gif
[https_leetcode-cn.com_problems_single-number]: https://link.zhihu.com/?target=https%3A//leetcode-cn.com/problems/single-number/