如何在数组中找到并返回重复的值

arr是字符串数组:

["hello", "world", "stack", "overflow", "hello", "again"]

有什么简单而优雅的方法来检查arr是否有重复项，如果有，返回其中一个(无论哪个)?

例子:

["A", "B", "C", "B", "A"]    # => "A" or "B"
["A", "B", "C"]              # => nil
154781 次浏览
小开

这样就可以了

arr = ["A", "B", "C", "B", "A"]
arr.inject(Hash.new(0)) { |h,e| h[e] += 1; h }.
select { |k,v| v > 1 }.
collect { |x| x.first }

也就是说，将所有值放到一个散列中，其中key是数组的元素，value是出现的次数。然后选择所有出现超过一次的元素。一件容易的事。

小开

你可以用几种方法做到这一点，第一种方法是最快的:

ary = ["A", "B", "C", "B", "A"]


ary.group_by{ |e| e }.select { |k, v| v.size > 1 }.map(&:first)


ary.sort.chunk{ |e| e }.select { |e, chunk| chunk.size > 1 }.map(&:first)

和O(N²)选项(即效率较低):

ary.select{ |e| ary.count(e) > 1 }.uniq
小开

Ruby数组对象有一个很棒的方法select。

select {|item| block } → new_ary
select → an_enumerator

你对第一种形式感兴趣。它允许您选择通过测试的对象。

Ruby数组对象还有另一个方法count。

count → int
count(obj) → int
count { |item| block } → int

在本例中，您感兴趣的是副本(在数组中出现多次的对象)。相应的测试是a.count(obj) > 1。

如果a = ["A", "B", "C", "B", "A"]，则

a.select{|item| a.count(item) > 1}.uniq
=> ["A", "B"]

你声明你只想要一个对象。所以选一个吧。

小开

只需找到第一个对象的索引(从左开始计数)不等于对象的索引(从右开始计数)的实例。

arr.detect {|e| arr.rindex(e) != arr.index(e) }

如果没有重复项，返回值将为nil。

我相信这是迄今为止在线程中发布的最快的解决方案，因为它不依赖于创建额外的对象，并且#index和#rindex是用C实现的。大o运行时是N^2，因此比Sergio的慢，但由于“慢”部分是用C运行的，所以墙壁时间可能会快得多。

小开
最佳答案 
a = ["A", "B", "C", "B", "A"]
a.detect{ |e| a.count(e) > 1 }

我知道这不是一个很优雅的回答，但我喜欢。这是漂亮的一行代码。工作得非常好，除非你需要处理庞大的数据集。

寻找更快的解决方案?给你!

def find_one_using_hash_map(array)
map = {}
dup = nil
array.each do |v|
map[v] = (map[v] || 0 ) + 1


if map[v] > 1
dup = v
break
end
end


return dup
end

它是线性的，O(n)，但是现在需要管理多行代码，需要测试用例等等。

如果你需要一个更快的解决方案，也许可以试试C。

这里是比较不同解决方案的要点:https://gist.github.com/naveed-ahmad/8f0b926ffccf5fbd206a1cc58ce9743e

小开

detect只找到一个副本。find_all将找到它们全部:

a = ["A", "B", "C", "B", "A"]
a.find_all { |e| a.count(e) > 1 }
小开

我知道这个帖子是专门关于Ruby的，但我在这里寻找如何在Ruby on Rails的背景下使用ActiveRecord来实现这一点，我想我也会分享我的解决方案。

class ActiveRecordClass < ActiveRecord::Base
#has two columns, a primary key (id) and an email_address (string)
end


ActiveRecordClass.group(:email_address).having("count(*) > 1").count.keys

上面返回一个数组，其中包含本例数据库表中重复的所有电子邮件地址(在Rails中为“active_record_classes”)。

小开

这里有另外两种找到复制品的方法。

使用套装

require 'set'


def find_a_dup_using_set(arr)
s = Set.new
arr.find { |e| !s.add?(e) }
end


find_a_dup_using_set arr
#=> "hello"

使用select代替find返回一个包含所有重复项的数组。

使用Array#difference

class Array
def difference(other)
h = other.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
reject { |e| h[e] > 0 && h[e] -= 1 }
end
end


def find_a_dup_using_difference(arr)
arr.difference(arr.uniq).first
end


find_a_dup_using_difference arr
#=> "hello"

删除.first以返回所有重复项的数组。

如果没有重复项，这两个方法都会返回nil。

I 提出Array#difference被添加到Ruby核心。更多信息在我的答案在这里中。

基准

让我们比较一下建议的方法。首先，我们需要一个数组进行测试:

CAPS = ('AAA'..'ZZZ').to_a.first(10_000)
def test_array(nelements, ndups)
arr = CAPS[0, nelements-ndups]
arr = arr.concat(arr[0,ndups]).shuffle
end

以及为不同的测试数组运行基准测试的方法:

require 'fruity'


def benchmark(nelements, ndups)
arr = test_array nelements, ndups
puts "\n#{ndups} duplicates\n"
compare(
Naveed:    -> {arr.detect{|e| arr.count(e) > 1}},
Sergio:    -> {(arr.inject(Hash.new(0)) {|h,e| h[e] += 1; h}.find {|k,v| v > 1} ||
[nil]).first },
Ryan:      -> {(arr.group_by{|e| e}.find {|k,v| v.size > 1} ||
[nil]).first},
Chris:     -> {arr.detect {|e| arr.rindex(e) != arr.index(e)} },
Cary_set:  -> {find_a_dup_using_set(arr)},
Cary_diff: -> {find_a_dup_using_difference(arr)}
)
end

我没有包括@JjP的答案，因为只有一个副本将被返回，当他/她的答案被修改为这样做时，它与@Naveed之前的答案相同。我也没有包括@Marin的回答，虽然在@Naveed的回答之前发布，但返回了所有的副本，而不是只有一个(一个小问题，但没有必要同时评估两个，因为当只返回一个副本时，它们是相同的)。

我还修改了其他返回所有重复项的答案，只返回找到的第一个重复项，但这对性能基本上没有影响，因为它们在选择一个重复项之前计算了所有重复项。

每个基准测试的结果从最快到最慢列出:

首先假设数组包含100个元素:

benchmark(100, 0)
0 duplicates
Running each test 64 times. Test will take about 2 seconds.
Cary_set is similar to Cary_diff
Cary_diff is similar to Ryan
Ryan is similar to Sergio
Sergio is faster than Chris by 4x ± 1.0
Chris is faster than Naveed by 2x ± 1.0


benchmark(100, 1)
1 duplicates
Running each test 128 times. Test will take about 2 seconds.
Cary_set is similar to Cary_diff
Cary_diff is faster than Ryan by 2x ± 1.0
Ryan is similar to Sergio
Sergio is faster than Chris by 2x ± 1.0
Chris is faster than Naveed by 2x ± 1.0


benchmark(100, 10)
10 duplicates
Running each test 1024 times. Test will take about 3 seconds.
Chris is faster than Naveed by 2x ± 1.0
Naveed is faster than Cary_diff by 2x ± 1.0 (results differ: AAC vs AAF)
Cary_diff is similar to Cary_set
Cary_set is faster than Sergio by 3x ± 1.0 (results differ: AAF vs AAC)
Sergio is similar to Ryan

现在考虑一个包含10,000个元素的数组:

benchmark(10000, 0)
0 duplicates
Running each test once. Test will take about 4 minutes.
Ryan is similar to Sergio
Sergio is similar to Cary_set
Cary_set is similar to Cary_diff
Cary_diff is faster than Chris by 400x ± 100.0
Chris is faster than Naveed by 3x ± 0.1


benchmark(10000, 1)
1 duplicates
Running each test once. Test will take about 1 second.
Cary_set is similar to Cary_diff
Cary_diff is similar to Sergio
Sergio is similar to Ryan
Ryan is faster than Chris by 2x ± 1.0
Chris is faster than Naveed by 2x ± 1.0


benchmark(10000, 10)
10 duplicates
Running each test once. Test will take about 11 seconds.
Cary_set is similar to Cary_diff
Cary_diff is faster than Sergio by 3x ± 1.0 (results differ: AAE vs AAA)
Sergio is similar to Ryan
Ryan is faster than Chris by 20x ± 10.0
Chris is faster than Naveed by 3x ± 1.0


benchmark(10000, 100)
100 duplicates
Cary_set is similar to Cary_diff
Cary_diff is faster than Sergio by 11x ± 10.0 (results differ: ADG vs ACL)
Sergio is similar to Ryan
Ryan is similar to Chris
Chris is faster than Naveed by 3x ± 1.0

注意，如果Array#difference是在C语言中实现的，那么find_a_dup_using_difference(arr)将会更有效，如果它被添加到Ruby核心中就是这样。

结论

很多答案是合理的，但使用Set显然是最好的选择。它在中等难度的情况下是最快的，在最困难的情况下是同样最快的，只有在计算上微不足道的情况下——当你的选择无论如何都无关紧要时——它才会被击败。

有一种非常特殊的情况，您可能会选择Chris的解决方案，即如果您想使用该方法分别去重复数千个小数组，并期望在其中找到一个通常小于10项的重复项。这将更快一点，因为它避免了创建Set的小额外开销。

小开 
a = ["A", "B", "C", "B", "A"]
b = a.select {|e| a.count(e) > 1}.uniq
c = a - b
d = b + c

结果

 d
=> ["A", "B", "C"]
小开

find_all ()返回一个array，其中包含block不是false的enum的所有元素。

来获取duplicate元素

>> arr = ["A", "B", "C", "B", "A"]
>> arr.find_all { |x| arr.count(x) > 1 }


=> ["A", "B", "B", "A"]

或复制uniq元素

>> arr.find_all { |x| arr.count(x) > 1 }.uniq
=> ["A", "B"]
小开

下面是我对一个大数据集的看法——比如一个用于查找重复部分的遗留dBase表

# Assuming ps is an array of 20000 part numbers & we want to find duplicates
# actually had to it recently.
# having a result hash with part number and number of times part is
# duplicated is much more convenient in the real world application
# Takes about 6  seconds to run on my data set
# - not too bad for an export script handling 20000 parts


h = {};


# or for readability


h = {} # result hash
ps.select{ |e|
ct = ps.count(e)
h[e] = ct if ct > 1
}; nil # so that the huge result of select doesn't print in the console
小开 
a = ["A", "B", "C", "B", "A"]
a.each_with_object(Hash.new(0)) {|i,hash| hash[i] += 1}.select{|_, count| count > 1}.keys

这是一个O(n)过程。

或者你也可以做下面的任何一行。也是O(n)但只有一次迭代

a.each_with_object(Hash.new(0).merge dup: []){|x,h| h[:dup] << x if (h[x] += 1) == 2}[:dup]


a.inject(Hash.new(0).merge dup: []){|h,x| h[:dup] << x if (h[x] += 1) == 2;h}[:dup]
小开

唉，大多数答案都是O(n^2)。

下面是一个O(n)解决方案，

a = %w{the quick brown fox jumps over the lazy dog}
h = Hash.new(0)
a.find { |each| (h[each] += 1) == 2 } # => 'the"

它的复杂度是多少?

  • 运行在O(n)中，并在第一次匹配时中断
  • 使用O(n)内存，但只使用最少的内存

现在，根据数组中重复项的频率，这些运行时实际上可能会变得更好。例如，如果大小为O(n)的数组已从k << n不同元素的总体中采样，只有运行时和空间的复杂度变为O(k)，然而更有可能的情况是，原始发布者正在验证输入并希望确保没有重复的输入。在这种情况下，运行时和内存复杂度都O(n)，因为我们希望大多数输入的元素没有重复。

小开 
r = [1, 2, 3, 5, 1, 2, 3, 1, 2, 1]


r.group_by(&:itself).map { |k, v| v.size > 1 ? [k] + [v.size] : nil }.compact.sort_by(&:last).map(&:first)
小开

如果你正在比较两个不同的数组(而不是一个数组对其自身)，一个非常快速的方法是使用Ruby的Array类提供的相交运算符&。

# Given
a = ['a', 'b', 'c', 'd']
b = ['e', 'f', 'c', 'd']


# Then this...
a & b # => ['c', 'd']
小开

each_with_object是你的朋友!

input = [:bla,:blubb,:bleh,:bla,:bleh,:bla,:blubb,:brrr]


# to get the counts of the elements in the array:
> input.each_with_object({}){|x,h| h[x] ||= 0; h[x] += 1}
=> {:bla=>3, :blubb=>2, :bleh=>2, :brrr=>1}


# to get only the counts of the non-unique elements in the array:
> input.each_with_object({}){|x,h| h[x] ||= 0; h[x] += 1}.reject{|k,v| v < 2}
=> {:bla=>3, :blubb=>2, :bleh=>2}
小开
< p > <代码> (1、2、3).uniq ! .nil吗?=比;真正的 (1、2、3、3).uniq ! .nil吗?=比;假 < /代码> < / p >

注意上面是破坏性的

小开

我需要找出有多少个重复，它们是什么，所以我写了一个函数建立在Naveed之前发布的:

def print_duplicates(array)
puts "Array count: #{array.count}"
map = {}
total_dups = 0
array.each do |v|
map[v] = (map[v] || 0 ) + 1
end


map.each do |k, v|
if v != 1
puts "#{k} appears #{v} times"
total_dups += 1
end
end
puts "Total items that are duplicated: #{total_dups}"
end
小开
  1. 让我们创建一个复制方法，将数组元素作为输入
  2. 在方法体中，让我们创建两个新的数组对象，一个是可见的，另一个是重复的
  3. 最后，让我们遍历给定数组中的每个对象，并在每次迭代中找到所见数组中存在的对象。
  4. 如果对象存在于seen_array中，则认为它是重复对象，并将该对象推入duplication_array
  5. 如果对象在seen中不存在，则认为它是唯一对象，并将该对象推入seen_array

让我们在代码实现中进行演示

def duplication given_array
seen_objects = []
duplication_objects = []


given_array.each do |element|
duplication_objects << element if seen_objects.include?(element)
seen_objects << element
end


duplication_objects
end

现在调用复制方法并输出返回result -

dup_elements = duplication [1,2,3,4,4,5,6,6]
puts dup_elements.inspect
小开

这段代码将返回重复值的列表。散列键是一种有效的检查已经看到的值的方法。根据是否看到value，原始数组ary被划分为2个数组:第一个数组包含唯一值，第二个数组包含重复值。

ary = ["hello", "world", "stack", "overflow", "hello", "again"]


hash={}
arr.partition { |v| hash.has_key?(v) ? false : hash[v]=0 }.last.uniq


=> ["hello"]

你可以进一步缩短它——尽管代价是语法稍微复杂一点——变成这样:

hash={}
arr.partition { |v| !hash.has_key?(v) && hash[v]=0 }.last.uniq
小开

Ruby 2.7引入了Enumerable#tally

你可以这样用:

ary = ["A", "B", "C", "B", "A", "A"]


ary.tally.select { |_, count| count > 1 }.keys
# => ["A", "B"]

ary = ["A", "B", "C"]


ary.tally.select { |_, count| count > 1 }.keys
# => []
小开

这运行得非常快(迭代了2.3mil id，不到一秒钟就把dup推到它们自己的数组中)

必须在工作中这样做，我将2.3 mil id导入到一个文件中，我将列表导入为排序，也可以由ruby排序。

list = CSV.read(path).flatten.sort
dup_list = []
list.each_with_index do |id, index|
dup_list.push(id) if id == list[index +1]
end
dup_list.to_set.to_a
小开 
def duplicates_in_array(array)
hash = {}
duplicates_hash = {}


array.each do |v|
hash[v] = (hash[v] || 0 ) + 1
end


hash.keys.each do |hk|
duplicates_hash[hk] = hash[hk] if hash[hk] > 1
end


return duplicates_hash
end

这将返回一个包含数组中每个副本的散列，以及它被复制的时间

例如:

array = [1,2,2,4,5,6,7,7,7,7]


duplicates_in_array(array)


=> {2=>2, 7=>4}

提交答案