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

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

总第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的真值表如下:

A B
F F F
F T T
T F T
T T F

动画演示

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

进阶版

有一个 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/ 

掏空小吴计划

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

 / 今日问题 / 


你还见过哪些可以通过 异或 的方法来解决的题目?


留言格式 —— Day xx : blablabla 这里再次强调下 ,不符合主题和格式的打卡无效噢 !不要到兑换的时候尴尬呀!小吴已经开始在excel表格一个个整理了噢,后续考虑透明化打卡。无效的留言目前小吴还是一个个回复说了无效,今后不说了,不精选就是无效!毕竟有效留言也可以相互学习啊,你说呢?



往期推荐:

21天,在Github上获取 6300 star

  这些奇葩的排序算法,你没见过动画吧?

  

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

欢迎关注这个会做动画的程序员👆

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 一道让你拍案叫绝的算法题

我还会在以下平台发布内容

GitHub 哔哩哔哩