如何检查一个数组是否有重复元素？

Question

我有一个数组A，想要检查它是否包含重复的值。我该怎么做？

- Skizit

---

“marked as duplicate”这个词组跟问题本身有些元话题。 - cpursley

“如何检查数组中是否有重复项？”并不完全等同于“如何在数组中查找并返回重复的值？”这个问题是在询问如何确定数组的唯一性，而另一个问题则是在询问如何从数组中提取重复的值。我认为它不应该被标记为重复--但另一个问题是类似的，应该在评论中链接。 - emery

但讽刺的是，这不是很富有吗？ - omikes

Answer 1

调用uniq函数（它返回一个没有重复元素的新数组）， 然后判断uniq后的数组是否比原始数组元素少：

if a.uniq.length == a.length
  puts "a does not contain duplicates"
else
  puts "a does contain duplicates"
end

请注意，数组中的对象需要适当地响应hash和eql?才能使uniq正常工作。

- sepp2k

---

此外，如果未找到重复项，则 uniq！ 将返回 nil 并更改 self 以删除重复项。有很多数组方法可用：http://ruby-doc.org/core/classes/Array.html - David

当然，如果它们对eql?没有有意义的响应，那么"重复"到底是什么意思呢？一旦你定义了eql?，hash也应该与之一致。 - Karl Knechtel

@Karl：这个数组中的两个元素==相等吗？ - sepp2k

为了好奇，为什么你使用 a.uniq.length == a.length 而不是简单地使用 a.uniq == a？ - Paul Hoffer

@phoffer，检查大小更快。 - Nakilon

Answer 2

为了找到重复的元素，我使用以下方法（使用 Ruby 1.9.3）：

array = [1, 2, 1, 3, 5, 4, 5, 5]
=> [1, 2, 1, 3, 5, 4, 5, 5]
dup = array.select{|element| array.count(element) > 1 }
=> [1, 1, 5, 5, 5]
dup.uniq
=> [1, 5]

- jmonteiro

---

选择 { array.count } 是一个嵌套循环，你正在为可以在 O(n) 中完成的事情执行 O(n^2) 复杂算法。 - apeiros

你说得对，为了解决Skizit的问题，我们可以使用O(n)算法; 但是为了找出哪些元素是重复的，我目前只能想到一个O(n^2)算法。 - jmonteiro

对于 n log n 的排序和去除连续重复项。 - user3125280

@apeiros，你的O(n)答案在哪里？ - alex88

@alex88 我没有提供答案，因为其他人已经回答了。例如sepp2k的答案：https://dev59.com/SG855IYBdhLWcg3wbjrO#4351408 - apeiros

Answer 3

如果您想返回重复项，可以这样做:

dups = [1,1,1,2,2,3].group_by{|e| e}.keep_if{|_, e| e.length > 1}
# => {1=>[1, 1, 1], 2=>[2, 2]}

如果您只想获取值：

dups.keys
# => [1, 2]

如果您想要查找重复项的数量：

dups.map{|k, v| {k => v.length}}
# => [{1=>3}, {2=>2}]

- Benjamin Crouzier

---

.group_by{|e| e} is equivalent to .group_by(&:itself) - Nathan Gouy

Answer 4

如果使用超过一次，可能需要对 Array 进行猴子补丁：

class Array
  def uniq?
    self.length == self.uniq.length
  end
end

然后：

irb(main):018:0> [1,2].uniq?
=> true
irb(main):019:0> [2,2].uniq?
=> false

- fakeleft

---

我建议避免使用猴子补丁来包装一行代码。 - Justin Force

猴子补丁确实容易出问题。 - Victor Martins

@sidewaysmilk 为什么要避免这种做法？它看起来像 Ruby 的方式：优雅、动态和干燥。 - hamstar

一个（主要？）原因是，如果你在代码中使用它，并且其他人（例如gems）也使用了你的猴子补丁，那么这可能会导致意外行为。所以我想我应该加一个说明，这只应该在你自己使用的代码中使用，并且在一个易于记忆的位置（例如一个monkey_patch.rb文件），这样你就不必花费太多时间寻找修改默认行为的代码。 - fakeleft