如何有效地提取Ruby数组中的重复元素?
我有一个类似[1,1,1,2,4,6,3,3]的数组,我希望得到重复元素的列表,在本例中为[1,3]。 我写了这个:
my_array.select{|obj|my_array.count(obj)>1}.uniq
但它的效率很低(o(n²))。 你有更好的主意吗? 如果可能简洁。
谢谢
灵感来自Ilya Haykinson的回答:
def repeated(array) counts = Hash.new(0) array.each{|val|counts[val]+=1} counts.reject{|val,count|count==1}.keys end
使用Ruby的Set库:
require 'set' ary = [1,1,1,2,4,6,3,3] dups = Set.new test_set = Set.new ary.each {|val| dups.add(val) unless test_set.add?(val)} dups.to_a # [1, 3]
我相信这应该是O(n),因为Set#add和Set#add? 据我所知,是恒定时间操作。
这样的事怎么样? 它将在O(n)中运行。
a = [1,1,1,2,4,6,3,3] b = {} a.each { |v| if b.has_key? v then b[v] = b[v]+1 else b[v]=1 end } b.reject { |k,v| if v > 1 then false else true end }.keys
AO(n)解决方案(将<< x
更改为+ [x]
并update
为merge
以使其纯粹起作用):
rs = xs.inject([[], {}]) do |(out, seen), x| [(seen[x] == 1 ? (out << x) : out), seen.update(x => (seen[x] || 0)+1)] end[0]
一种更简单但更节省空间的方法:
rs = xs.group_by { |x| x }.select { |y, ys| ys.size > 1 }.keys
使用“list-comprehension”避免中间哈希的相同想法:
rs = xs.group_by { |x| x }.map { |y, ys| y if ys.size > 1 }.compact
使用inject
[1,1,1,2,4,6,3,3].inject({}){ |ele, n| ele[n] = nil; ele }.keys # => [1, 2, 4, 6, 3]
说明:
ele
hash将其初始化为{}
,每次迭代时,将具有数字n
和nil
值的键添加到ele
哈希中。 最后ele
返回:
{1=>nil, 2=>nil, 4=>nil, 6=>nil, 3=>nil}
我们只想要密钥,所以.keys
结束了工作。
一些想法:你必须弄清楚正确的库数据结构:
1对数组O(nlogn)进行排序,然后运行数组
2创建一个集合,搜索集合中的当前数组元素,如果未找到,则插入并继续处理所有元素 – O(nlogn)。
我在考虑计算一个独特元素在数组中出现的次数。 它可能是非常低效的,就像最初的建议一样,但看起来很有趣。 我没有在大型arrays上做任何基准测试,所以这只是一个练习。
a = [1,1,1,2,4,6,3,3] dupes = [] a.uniq.each do |u| c = a.find_all {|e| e == u}.size dupes << [u, c] unless c == 1 end puts dupes.inspect # dupes = [[1, 3], [3, 2]] # 1 appears 3 times # 3 appears twice # to extract just the elment a bit cleaner dupes = a.uniq.select do |u| a.find_all {|e| e == u}.size != 1 end puts dupes.inspect # returns [1,3]
如果重复的条目总是连续的,这将在您的示例中起作用; 否则你必须先排序。 each_cons检查指定大小的滚动窗口。
require 'set' my_array = [1,1,1,2,4,6,3,3] dups = Set.new my_array.each_cons(2) {|a,b| dups.add(a) if (a == b)} p dups.to_a
- 使用Ocra,LoadError从ruby文件生成可执行文件?
- 什么|| =在Ruby中意味着什么?
- Rails应用程序错误 – ActiveRecord :: PendingMigrationError正在等待迁移; 运行’rake db:migrate RAILS_ENV = development’来解决此问题
- Rails 4.2.0中的简单整数赋值的RangeError应该通过validation捕获
- 将HTML转换为纯文本(包含)
- 以CSV格式导出SQLite3表的内容
- 无法在MAC OS X 10.9.2上安装rails
- 什么是|| =ruby?
- 为什么Ruby open-uri打开在我的unit testing中返回一个StringIO,但在我的控制器中是一个FileIO?