微信号:TheAlgorithm

介绍:算法与数据结构知识、资源分享

分享一道解法巧妙的算法题

2019-03-13 22:03 帅地

来自:苦逼的码农(微信号:di201805)

作者:帅地

个人简介:一个热爱编程的在校生,我的世界不只有coding,还有writing。目前维护订阅号「苦逼的码农」,专注于写「算法与数据结构」,「Java」,「计算机网络」。

最近碰到很多通过巧妙着运用位运算来巧妙解决复杂问题的算法,今天分享的这道题,或许能够开拓你的一些算法思维。

题目描述

有一组存放 ID 的数据。并且 ID 取值为 0 - (N-1) 之间,其中只有一个 ID 出现的次数为 1,其他的 ID 出现的次数都等于 2,问如何找到这个次数为 1 的 ID ?

解法一:巧用数组下标

不知道有多少人还记得我之前分享的巧用数组下标的技巧:一些常用的算法技巧总结

我的第一想法便是采用下标法来解决,把 ID 作为数组 arr 的下标,在遍历 ID 的过程中,用数组记下每个 ID 出现的次数,即每次遍历到 ID = n,则 arr[n]++。

之后我们在遍历数组 arr,找到 arr[n] = 1 的ID,该下标 n 便是我们要寻找的目的 ID。

这种方法的时间复杂度为 O(N),空间复杂度为 O(N)。

解法二:巧用哈希表

显然时间复杂度是无法再降低的了,因为我们必须要遍历所有的 ID,所以时间复杂度最少都得为 O(N)了,所以我们要想办法降低空间复杂度。

大家想一个问题,假如我们检测到某个 ID 已经出现了 2 次了,那么这个 ID 的数据我们还需要存储记录吗?大部分的 ID 都出现了 2 次,这一大部分的数据真的需要存储吗?

答是不用的,因为出现 2 次的 ID 不是我们所要找的。所以我们可以优化解法一,我们可以采用哈希表来记录 ID 出现的次数:利用哈希表记下每个 ID 出现的次数,每次遇见一个 ID,就把这个 ID 放进 哈希表,如果这个 ID 出现了次数已经为 2 了,我们就把这个 ID 从哈希表中移除,最后哈希表只会剩下一个我们要寻找的 ID。

这个方法最好的情况下空间复杂度可以降低到 O(1),最坏的情况仍然了 O(N)。

解法三:巧用位运算

那究竟有没办法让空间复杂度在最坏的情况下也是 O(1) 呢?

答是有的,按就是采用异或运算。异或运算有个特点:

异或运算特点:相同的两个数异或之后,结果为 0,任何数与0异或运算,其结果不变并且,异或运算支持结合律

所以,我们可以把所有的 ID 进行异或运算,由于那些出现两次的 ID 通过异或运算之后,结果都为 0,而出现一次的 ID 与 0 异或之后不变,又因为异或支持结合律,所以,把所有 ID 进行异或之后,最后的结果便是我们要找的 ID。

这个方法的空间复杂度为 O(1),巧妙利用了位运算,而且运算的效率是非常高效的。

问题拓展

假如有 2 个 ID 出现的次数为 1,其他 ID 出现的次数都为 2 呢?有该如何解决呢?是否还是可以用位运算呢?

为了方便这里我们先假设 异或 的符号为 @,

答是必须的,假如这两个出现一次的 ID 分别为 A, B,则所有 ID 异或后的结果为 A@B,这时我们遇到的问题是无法确定 A,B的值。

由于 A 和 B 是不一样的值,所以 A@B 的结果不为 0,也就是说,这个异或值的二进制中某一位为1。显然,A 和 B 中有且仅有一个数的相同位上也为 1。

这个时候,我们可以把所有 ID 分为两类,一类在这个位上为 1,另一类为 0,那么对于这两类,一类会含有 A,另一类会含有 B。于是,我们可以分别计算这两类 ID 的异或值,几可得到 A 和 B 的值。

总结

大家做刷题的时候,不妨多加上一个想法:是否可以用的上位运算这种思路。有收获?不妨来个好看让更多人看到这篇文章!


●编号869,输入编号直达本文

●输入m获取文章目录

推荐↓↓↓

程序员求职面试

更多推荐25个技术类公众微信

涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。

 
算法与数据结构 更多文章 春招已近,这份GitHub万星的ML算法面试大全请收下 为什么我不建议你买保险? 算法科普:有趣的霍夫曼编码 2019,想转行人工智能?美国哈佛博士后有话说。。。 2019年2月份GitHub上最热门的开源项目
猜您喜欢 平安金融壹帐通测试技术周报(第四十二期) 全球遭受大规模勒索软件攻击:涉及近100个国家! 知识点归纳(1) 怎样收智商税 AI 玩跳一跳的正确姿势,Auto-Jump 算法详解