如何合并数组中的连续重复元素?
我需要合并一个数组中的连续重复元素
[1, 2, 2, 3, 1]
变
[1, 2, 3, 1]
#uniq
不能用于此目的。 为什么? 因为#uniq
会产生这个:
[1, 2, 3]
def remove_consecutive_duplicates(xs) [xs.first] + xs.each_cons(2).select do |x,y| x != y end.map(&:last) end remove_consecutive_duplicates([1, 2, 2, 3, 1]) #=> [1,2,3,1]
这将返回一个像uniq
一样的新数组,并在O(n)
时间内工作。
核心中有一个抽象,几乎可以完成工作, Enumerable#chunk :
xs = [1, 2, 2, 3, 3, 3, 1] xs.chunk { |x| x }.map(&:first) #=> [1, 2, 3, 1]
sepp2k的答案已被接受,但这里有一些替代方案:
# Because I love me some monkeypatching class Array def remove_consecutive_duplicates_2 # Because no solution is complete without inject inject([]){ |r,o| r << o unless r.last==o; r } end def remove_consecutive_duplicates_3 # O(2n) map.with_index{ |o,i| o if i==0 || self[i-1]!=o }.compact end def remove_consecutive_duplicates_4 # Truly O(n) result = [] last = nil each do |o| result << o unless last==o last = o end result end end
虽然性能不是一切,但这里有一些基准:
Rehearsal -------------------------------------------- sepp2k 2.740000 0.010000 2.750000 ( 2.734665) Phrogz_2 1.410000 0.000000 1.410000 ( 1.420978) Phrogz_3 1.520000 0.020000 1.540000 ( 1.533197) Phrogz_4 1.000000 0.000000 1.000000 ( 0.997460) ----------------------------------- total: 6.700000sec user system total real sepp2k 2.780000 0.000000 2.780000 ( 2.782354) Phrogz_2 1.450000 0.000000 1.450000 ( 1.440868) Phrogz_3 1.530000 0.020000 1.550000 ( 1.539190) Phrogz_4 1.020000 0.000000 1.020000 ( 1.025331)
基准测试从删除orig = (0..1000).map{ rand(5) }
10,000次重复项。
没有!uniq
对你正在做的事情不起作用?
http://ruby-doc.org/docs/ProgrammingRuby/html/ref_c_array.html