[LeetCode]260. Single Number III 孤独的数字 第三季

题目地址:

https://leetcode.com/problems/single-number-iii/

题目描述:

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

题目大意:

提供一个装有一些数字的数组 nums ,其中一定有两个元素只显示一次,与此同时其他的元素显示两次。寻找到这两个只显示一次的元素。

比如说:

提供一个数组 nums = [1, 2, 1, 3, 2, 5], 返回[3, 5].


 

有了上一次第一季(136. Single Number)的前车之鉴,我知道两层 for 循环机器是不会放过我的。所以我只能先手上网找找有没有什么好的解决办法。毕竟记录个数的一定有它类似的解法。

于是我发现了这个网页:https://kelvinmao.github.io/136.Single-Number/

找到了我想要的东西,哈希表。

“(引用)

对于这个题而言,另一种解法是使用hash-table,先建立哈希表,然后遍历数组中的元素,如果该元素不在表中,则将其插入表中;否则将其删除,最后返回表中唯一一个元素即可,代码如下:

然后我就仿照着哈希表的用法写出了我的答案:

第一次编译的时候编译超时。然后我再给他提交了一次,就Accept了。不过我实在想不明白,如果不用这种记录员的笨办法,还有没有其他的解法。必然是用异或,可是异或的话,最后都不知道会出来什么东西了。

然后我再查了一下答案库。发现人家真是牛。答案地址:http://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/72983

“(引用)

题解

Single Number 的 follow up, 不妨设最后两个只出现一次的数分别为 x1, x2. 那么遍历数组时根据两两异或的方法可得最后的结果为 x1 ^ x2, 如果我们要分别求得 x1x2, 我们可以根据 x1 ^ x2 ^ x1 = x2 求得 x2, 同理可得 x_1. 那么问题来了,如何得到x1x2呢?看起来似乎是个死循环。大多数人一般也就能想到这一步(比如我…)。(呵呵呵博主我怎么没想到)

这道题的巧妙之处在于利用x1 ^ x2的结果对原数组进行了分组,进而将x1x2分开了。具体方法则是利用了x1 ^ x2不为0的特性,如果x1 ^ x2不为0,那么x1 ^ x2的结果必然存在某一二进制位不为0(即为1),我们不妨将最低位的1提取出来,由于在这一二进制位上x1x2必然相异,即x1, x2中相应位一个为0,另一个为1,所以我们可以利用这个最低位的1将x1x2分开。又由于除了x1x2之外其他数都是成对出现,故与最低位的1异或时一定会抵消,十分之精妙!

(这段话看似绕口,不易理解。博主花了挺久的时间去思考这段话。最后明白了他所说的最低位的 1 的意思。如: 1011 的最低位的 1 就是最后一位,而 1010 的最低位的 1 是倒数第二位。)

源码分析

求一个数二进制位1的最低位方法为 x1xorx2 - (x1xorx2 & (x1xorx2 - 1)), 其他位运算的总结可参考 Bit Manipulation。利用last1Bit可将数组的数分为两组,一组是相应位为0,另一组是相应位为1.

最后要总结的是,像个记录员拿表格记录并不需要 for 循环,要懂得使用STL库里的东西。然后可以通过一些特殊的情况为数字分组,再进行计算。(其实一开始思考的时候就是想把数字分成两组,可是怎么分都不太合适)。

评论已关闭。