[广告: 最高 ¥2000 红包]阿里云服务器, 主机等产品通用, 可叠加官网常规优惠使用 | 限时领取
翻译: 码中人
在数组中找到唯一的数字, 听起来很简单吧!
一句话描述可能会产生误导, 那我们就从一个具体的数组开始:
[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)
按位异或有两个步骤:
将运算数变成一个有符号的 32 位二进制数.
返回一个新的数字, 规则如下: 如果两个比特都是 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).
总结
在一个包含成对相同数字的数组中寻找一个唯一的值是一个小问题. 这个问题本身并不十分有趣, 也没有具体的应用场景, 可能只在面试时被问到.
在这篇文章中, 我们使用了两种在线性时间内解决它的方法. 希望你能借此了解按位异或这个小技巧.
:).
来源: https://www.mzh.ren/how-to-find-a-unique-number-in-a-list-of-pairs.html