arr是字符串数组,例如:["hello", "world", "stack", "overflow", "hello", "again"].
什么是简单而优雅的方法来检查是否arr有重复,如果是,则返回其中一个(无论哪个).
例子:
["A", "B", "C", "B", "A"] # => "A" or "B"
["A", "B", "C"] # => nil
Nav*_*eed 233
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)但现在需要管理多个LOC,需要测试用例和东西!
如果您需要更快的解决方案,可以尝试C代替:)
以下是比较不同解决方案的gits:https://gist.github.com/naveed-ahmad/8f0b926ffccf5fbd206a1cc58ce9743e
Rya*_*pte 208
您可以通过几种方式完成此操作,第一个选项是最快的:
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 ^ 2)选项(即效率较低):
ary.select{ |e| ary.count(e) > 1 }.uniq
Chr*_*ald 43
只需找到第一个实例,其中对象的索引(从左边开始计数)不等于对象的索引(从右边开始计数).
arr.detect {|e| arr.rindex(e) != arr.index(e) }
如果没有重复项,则返回值为nil.
我相信这是最快的解决方案张贴在线程到目前为止,为好,因为它不依赖于创造更多的对象,并且#index和#rindex在C中实现的大O的运行时间为N ^ 2,因此慢塞尔吉奥,但由于"缓慢"的部分在C中运行,因此可以更快地打开时间.
小智 27
detect只发现一个重复.find_all会发现它们全部:
a = ["A", "B", "C", "B", "A"]
a.find_all { |e| a.count(e) > 1 }
Car*_*and 20
以下是另外两种查找副本的方法.
使用一套
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如果没有重复,则两种方法都返回.
我建议将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
请注意,find_a_dup_using_difference(arr)如果Array#difference在C中实现它会更有效,如果它被添加到Ruby核心就是这种情况.
结论
许多答案都是合理的,但使用Set是明智的选择.它在中等难度的情况下是最快的,在最困难的情况下联合最快,并且只在计算上微不足道的情况下 - 当你的选择无论如何都无关紧要 - 它是否可以被打败.
你可以选择克里斯解决方案的一个非常特殊的情况是,如果你想使用这个方法分别去除数千个小数组,并期望找到通常少于10个项目的副本.这会更快一点因为它避免了创建Set的额外开销.
aku*_*uhn 17
唉,大多数答案都是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)因为我们期望元素对大多数输入没有重复.
mec*_*cov 16
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
# => []
Ruby 2.7也引入了Enumerable#filter_map，可以组合这些方法
ary = ["A", "B", "C", "B", "A", "A"]
ary.tally.filter_map { |el, count| el if count > 1 }
# => ["A", "B"]
Mar*_*lez 14
Ruby Array对象有一个很棒的方法select.
select {|item| block } ? new_ary
select ? an_enumerator
第一种形式是你在这里感兴趣的.它允许您选择通过测试的对象.
Ruby Array对象有另一种方法,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 = ["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是出现次数.然后选择多次出现的所有元素.简单.
我知道这个线程是专门针对Ruby的,但是我在这里找到了如何在使用ActiveRecord的Ruby on Rails的上下文中执行此操作,并且我认为我也会分享我的解决方案.
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").
find_all()返回一个array包含的所有元素enum为哪些block不是false.
获得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"]
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]