Ruby -查找两个数组中不相同的元素
Ruby -查找两个数组中不相同的元素
提问于 2013-11-25 14:47:05
我一直在考虑下面的一个问题--有两个数组，我需要找到它们都不常见的元素，例如：
a = [1,2,3,4]
b = [1,2,4]预期的答案是[3]。
到目前为止我一直是这样做的：
a.select { |elem| !b.include?(elem) }但它给了我O(N ** 2)的时间复杂性。我相信可以做得更快;)
另外，我一直在考虑这样做(使用与&相反的方法，它提供了两个数组的公共元素)：
a !& b #=> doesn't work of course另一种方法可能是添加两个数组并使用类似于uniq的方法查找唯一元素，以便：
[1,1,2,2,3,4,4].some_method #=> would return 3回答 4
Stack Overflow用户
回答已采纳
发布于 2013-11-25 15:31:27
最简单的解决方案(就只使用已经存在的数组和库存数组方法而言)是友联市 of 差异。
a = [1,2,3,4]
b = [1,2,4]
(a-b) | (b-a)
=> [3]这可能比O(n**2)更好，也可能不会更好。还有其他选项可能会提供更好的绩效(见其他答案/评论)。
编辑:下面是排序和迭代方法的一个快速实现(这假设数组没有重复的元素，否则它将需要修改，这取决于在这种情况下需要什么样的行为)。如果有人能想出更短的方法来做这件事，我会感兴趣的。限制因素是所使用的类型。我假设Ruby使用某种快速排序，因此复杂度平均为O(n log n)，可能是O(n**2)的最坏情况；如果数组已经排序，那么当然可以删除对sort的两个调用，并在O(n)中运行。
def diff a, b
a = a.sort
b = b.sort
result = []
bi = 0
ai = 0
while (ai < a.size && bi < b.size)
if a[ai] == b[bi]
ai += 1
bi += 1
elsif a[ai]<b[bi]
result << a[ai]
ai += 1
else
result << b[bi]
bi += 1
end
end
result += a[ai, a.size-ai] if ai<a.size
result += b[bi, b.size-bi] if bi<b.size
result
endStack Overflow用户
发布于 2013-11-25 15:19:53
正如@iamnotmaynard在注释中所指出的，这传统上是一种集合操作(称为对称差异)。Ruby的Set类包含了这个操作，因此表达它的最惯用的方法是使用Set：
Set.new(a) ^ b这应该会给O(n)性能(因为集合成员资格测试是常数时间)。
Stack Overflow用户
发布于 2013-11-25 15:09:22
a = [1, 2, 3]
b = [2, 3, 4]
a + b - (a & b)
# => [1, 4]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20205023
复制相关文章
相似问题
注册服务和广播接收器时的异常
可能失败的函数的接收器参数和移动语义(强异常安全性)
无法启动接收器异常
输出参数和异常
参数和接收器有什么区别？
添加站长 进交流群
领取专属 10元无门槛券
AI混元助手 在线答疑
关注 腾讯云开发者公众号
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
