首先考虑每个元素都在A中的情况,就像问题的例子一样,B中的每个元素都在A中:
B
。
A = [1,2,3,4,5,6,7,8,9,10]
B = [3,6,1,5,1,2,1,6]
可以这样写,只需要对A
进行一次遍历(构建g
1),并对B
进行一次遍历。
g = A.each_with_object({}) { |n,h| h[n] = 1 }
B.each_with_object(g) { |n,h| h[n] += 1 }.flat_map { |k,v| [k]*(v-1) }
如果不能保证
B
的所有元素都在
A
中,并且不在其中的任何元素都将放置在排序数组的末尾,则可以稍微更改
g
的计算方式。
g = (A + (B-A)).each_with_object({}) { |n,h| h[n] = 1 }
这需要再经过A和B各一次。
例如,假设:
A = [2,3,4,6,7,8,9]
并且B
保持不变。然后,
g = (A + (B-A)).each_with_object({}) { |n,h| h[n] = 1 }
B.each_with_object(g) { |n,h| h[n] += 1 }.flat_map { |k,v| [k]*(v-1) }
这个解决方案展示了Ruby v1.9中有争议的哈希属性更改的价值:哈希表从此保证维护键插入的顺序。
1 我认为可以写成
g = A.product([1]).to_h
,但是文档
Array#to_h不能保证返回的哈希表中键的顺序与
A
中的顺序相同。