Ruby – 数组交集（带有重复项）
我有array(1 and 2) 。 我如何从中获取array3 ？
array1 = [2,2,2,2,3,3,4,5,6,7,8,9] array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0] array3 = [2,2,2,3,4,8]
array1 & array2返回[2,3,4,8] ，但我需要保留重复项。
(array1 & array2).flat_map { |n| [n]*[array1.count(n), array2.count(n)].min } #=> [2,2,2,3,4,8]
步骤：
a = array1 & array2 #=> [2, 3, 4, 8]
（ 2 ）的第一个元素被传递给块并分配给块变量：
n = 2
并执行块计算：
[2]*[array1.count(2), array2.count(2)].min #=> [2]*[4,3].min #=> [2]*3 #=> [2,2,2]
所以2被映射到[2,2,2] 。 对于a的其余三个元素，计算类似。 当我使用flat_map ，返回[2,2,2,3,4,8] 。
你难以记住Enumerable＃flat_map与Enumerable #map的不同之处吗？ 假设我使用的是map而不是flat_map 。 然后
a.map { |n| [n]*[array1.count(n), array2.count(n)].min } #=> [[2, 2, 2], [3], [4], [8]]
flat_map不会在每个数组前面放置一个splat：
[*[2, 2, 2], *[3], *[4], *[8]] #=> [2, 2, 2, 3, 4, 8]
如果数组array1和array2很大并且效率是一个问题，我们可以做一些O（N）预处理：
def cnt(arr) arr.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 } end cnt1 = cnt(array1) #=> {2=>4, 3=>2, 4=>1, 5=>1, 6=>1, 7=>1, 8=>1, 9=>1} cnt2 = cnt(array2) #=> {2=>3, 3=>1, 4=>4, 8=>2, 0=>3} (array1 & array2).flat_map { |n| [n]*[cnt1[n], cnt2[n]].min } #=> [2,2,2,3,4,8]
这很有趣; Cary的flat_map解决方案特别聪明。 这是使用常规旧map的替代each_with_object并在each_with_object帮助each_with_object ：
array1.each_with_object(array2.dup).map{|v,t| v if (l = t.index v) && t.slice!(l) }.compact #=> [2,2,2,3,4,8]
这里的复杂性很大程度上涉及内联体操，用于为map提供足够的信息来完成任务：
# # we want to duplicate array2 since we'll be # mutating it to track duplicates # \ array1 array2 # \ value copy # \ \ / array1.each_with_object(array2.dup).map{|v,t| ... } # | / # Enumerator for array1 Iterate over # with a copy of array2 Enumerator with map
我们可以使用each_with_object为array1提供一个Enumerator，它也为我们的方法链提供了对array2副本的访问。 然后Map可以遍历each_with_object Enumerator（引用array1），将每个值加载到局部变量v并将array2复制到局部变量t 。 从那里：
# map the value IF... # / it exists in and we were able to # / our array2 copy remove it from our copy # / | | map{|v,t| v if (l = t.index v) && t.slice!(l) }.compact # | \ \ | # array1 \ \ dump nils # value array2 \ # copy load index position into temporary variable l
我们遍历array1的每个值并搜索array2中是否存在该值（通过t ）。 如果它存在，我们从array2的副本中删除第一次出现的值，并将值map到我们的结果数组。
注意t.index(v)之前的t.index(v)检查t.slice!(t.index(v))用作短路保护，以防t （我们的array2副本）中的值不存在。 我们还使用了一个在线技巧，将索引值分配给局部变量l ： (l = t.index v)所以我们可以在随后的布尔检查中引用l ： t.slice!(l) 。
最后，因为只要array2中不存在array1值，此方法将映射nil值，我们compact结果以删除nils。
对于那些好奇的人，这里是迄今为止提出的解决方案的一些基准测试。 首先，以下是在样本arrays上执行100,000次操作的时钟速度：
Cary: 1.050000 0.010000 1.060000 ( 1.061217) Cary+: 1.580000 0.010000 1.590000 ( 1.603645) Cam: 0.550000 0.010000 0.560000 ( 0.552062) Mudasobwa: 2.540000 0.050000 2.590000 ( 2.610395) Sergii: 0.660000 0.000000 0.660000 ( 0.665408) Sahil: 1.750000 0.010000 1.760000 ( 1.769624) #Tommy: 0.290000 0.000000 0.290000 ( 0.290114)
如果我们扩展测试数组以保持10000个具有高度交叉的整数…
array1 = array2 = [] 10000.times{ array1 << rand(10) } 10000.times{ array2 << rand(10) }
并且循环100次，简单循环解决方案（Sahil）开始区分自己。 Cary的解决方案也很好用，特别是在预处理方面：
user system total real Cary: 1.590000 0.020000 1.610000 ( 1.615798) Cary+: 0.870000 0.010000 0.880000 ( 0.879331) Cam: 6.680000 0.090000 6.770000 ( 6.838829) Mudasobwa: 6.740000 0.080000 6.820000 ( 6.898394) Sergii: 6.760000 0.100000 6.860000 ( 6.962025) Sahil: 0.740000 0.030000 0.770000 ( 0.785975) #Tommy: 0.430000 0.010000 0.440000 ( 0.446482)
对于数组的1/10大小，1000个整数和低交点 ，但是......
array1 = array2 = [] 1000.times{ array1 << rand(10000) } 1000.times{ array2 << rand(10000) }
当我们循环10次时，flat_map解决方案变得平坦......除非我们使用预处理（Cary +）：
user system total real Cary: 135.400000 0.700000 136.100000 (137.123393) Cary+: 0.270000 0.010000 0.280000 ( 0.268255) Cam: 0.670000 0.000000 0.670000 ( 0.676438) Mudasobwa: 0.670000 0.010000 0.680000 ( 0.684088) Sergii: 0.660000 0.010000 0.670000 ( 0.673881) Sahil: 1.970000 2.130000 4.100000 ( 4.121759) #Tommy: 0.050000 0.000000 0.050000 ( 0.045970)
以下是基准测试的要点： https ： //gist.github.com/camerican/139463b4bd9e0fd89424377931042ce4
array1 = [2,2,2,2,3,3,4,5,6,7,8,9] array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0] a1, a2 = array1.dup, array2.dup # we'll mutate them loop.with_object([]) do |_, memo| break memo if a1.empty? || a2.empty? e = a2.delete_at(a2.index(a1.shift)) rescue nil memo << e if e end #⇒ [2,2,2,3,4,8]
array1 = [2,2,2,2,3,3,4,5,6,7,8,9] array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0]
获取示例数组中每个元素的频率：
a1_freq=Hash.new(0); a2_freq=Hash.new(0); dup_items=[]; array1.each {|a| a1_freq[a]+=1 } array2.each {|b| a2_freq[b]+=1 }
最后比较元素是否存在于另一个数组中。 如果是，则获取两个样本数组中找到的公共元素的最小计数。
a1_freq.each {|k,v| a2_freq[k] ? dup_items+=[k]*[v,a2_freq[k]].min : nil} #dup_items=> [2, 2, 2, 3, 4, 8]
这有点冗长，但假设您指的是值在同一位置的位置：
def combine(array1, array2) longer_array = array1.length > array2.length ? array1 : array2 intersection = [] count = 0 longer_array.each do |item| if array1 == longer_array looped_array = array2 else looped_array = array1 end if item == looped_array[count] intersection.push(item) end count +=1 end print intersection end array_1 = [2,2,2,2,3,3,4,5,6,7,8,9] array_2 = [2,2,2,3,4,4,4,4,8,8,0,0,0] combine(array_1, array_2)
我只想指出，我不知道你是如何得到数组3的，因为所有三个数组上的索引位置3都不同：
array_1[3] = 2 array_2[3] = 3 array_3[3] = 3
我将尝试以这种方式达到预期的结果：
array1, array2 = [array1, array2].sort_by(&:size) arr_copy = array2.dup array1.each.with_object([]) do |el, arr| index = arr_copy.find_index(el) arr << arr_copy.slice!(index) if index end # => [2, 2, 2, 3, 4, 8]