如何找到数组里面的唯一数字

[广告:最高 ¥2000 红包]阿里云服务器、主机等产品通用,可叠加官网常规优惠使用 | 限时领取

原文:How to find a unique number in a list containing pairs? – Yonatan Kra

翻译:码中人

在数组中找到唯一的数字,听起来很简单吧!

一句话描述可能会产生误导,那我们就从一个具体的数组开始:

[1,3,17,3,1]

以上给出的数组,唯一出现一次的数字是17,其余的数字1,3都出现过两次。接下来,我们就以这个数组为用例来测试解决办法。

有3种主要的方法可以找到这个唯一数。从性能上看,可能会是:

  • 时间复杂度O(n*n)
  • 时间复杂度O(n)和空间复杂度O(n)
  • 时间复杂度O(n)和空间复杂度O(1)空间

读完这篇文章后,你会知道这三种方法。

1 天真无邪法

让我们找出[1,3,17,3,1]中的唯一数字。很简单。

这个方案会检查所有的数字,并验证它们是不是重复的。最坏的情况是,我们对列表中的每个成员都进行一次检查。这意味着,时间复杂度为O(n*n)。

2 线性阶方法

在解决这类问题,我们通常希望以线性方式解决。方法是用对象字面量来记住哪些数字出现了不止一次。

我们创建一个叫memo对象,来存储出现数字的次数。然后我们在nums数组上进行迭代。如果这个数字是第一次出现,创建一个与数字同名属性,标记为1。如果再次遇到这个数字,就加1。

然后再遍历memo对象的属性,找到只出现1次的数。

这段代码没有嵌套循环,时间复杂度是线性的O(n)。但是我们创建了一个对象,它占用的内存为O(n/2)空间(实际上是O(n))。我们怎么样才能进一步优化呢?

3 按位异或(Bitwise XOR)

按位异或有两个步骤:

  1. 将运算数变成一个有符号的32位二进制数。
  2. 返回一个新的数字,规则如下:如果两个比特都是1或0,返回0。否则–返回1。

下面是一个例子。4 ^ 5

4在二进制中是100,而5是101。把它们变成32位,只是在左边垫上零。

最终,我们将需要对这两个二进制数字(100和101)进行异或,

1 and 1 => 0

0 and 0 => 0

0 and 1 => 1

结果是001,也就是1。而相同的数字相异或,如4^4,结果为0。

如果我们有一个包含成对数的数组,做下面的操作,结果是0。

[1,2,3,4,5,6,7,1000000,1,2,3,4,5,6,7,1000000].reduce((val, num) => val ^ num)

注意,是成对的数。

如果在以上数组中添加一个唯一的数,会怎么样?

[1,2,3,4,5,6,7,1000000,8,1,2,3,4,5,6,7,1000000].reduce((val, num) => val ^ num)

在按位异或时,相同的数字会抵销,有一个独特的值会 “脱颖而出”。同时,按位运算不用考虑元素的顺序。

现在我们有了一个线性方案,并且空间复杂度为O(1)。

总结

在一个包含成对相同数字的数组中寻找一个唯一的值是一个小问题。这个问题本身并不十分有趣,也没有具体的应用场景,可能只在面试时被问到。

在这篇文章中,我们使用了两种在线性时间内解决它的方法。希望你能借此了解按位异或这个小技巧。

:)。

码中人 微信公众号