如何有效地从正整数和负整数数组中删除正整数的负重复,如下所示:[1,5,10,5,-5,-1,9]因此,我希望:[1, 5,10,5,9](-1和-5被删除,因为它们是1和5的负重复)
这是我能找到的最简单的方法:
选择正数
计算他们的相反数字
从原始数组中删除它们
array = [1, 5, 10, 5, -5, -1, 9]
p array - array.select{ |i| i > 0 }.map{ |i| -i }
# [1, 5, 10, 5, 9]
它使用Array#-,应该相当快.
你可以O(n)通过对正数进行两次遍历,然后从数组中取消其绝对值为abs的数组负值来执行此操作:
def reject_neg_dups(arr)
positives = Hash[arr.map {|x| (x>0) ? [x,1] : nil }.compact]
arr.reject { |x| (x < 0) && positives[-x] }
end
reject_neg_dups([-1, 1, 2, -2]) # => [1, 2]
reject_neg_dups([-1, 1, -2]) # => [1, -2] since 2 does not appear
有趣的是,Array-解决方案比目前列出的其他解决方案要快得多:
require 'benchmark'
def reject_neg_dups_hash(arr)
positives = Hash[arr.map {|x| (x>0) ? [x,1] : nil }.compact]
arr.reject { |x| (x < 0) && positives[-x] }
end
def reject_neg_dups_include(arr)
arr.reject { |x| (x < 0) && arr.include?(x.abs) }
end
def reject_neg_dups_arrayminus(arr)
arr - arr.select { |i| i > 0 }.map { |i| -i }
end
def reject_neg_dups_arrayminusewo(arr)
arr - arr.each_with_object([]) { |n,b| b << -n if n > 0 }
end
arr = Array.new(1000) { rand(-100..100) }
N = 1000
Benchmark.bm(15) do |x|
x.report('Array-') { N.times { reject_neg_dups_arrayminus(arr.dup) } }
x.report('Array-ewo') { N.times { reject_neg_dups_arrayminusewo(arr.dup) } }
x.report('hash') { N.times { reject_neg_dups_hash(arr.dup) } }
x.report('include?') { N.times { reject_neg_dups_include(arr.dup) } }
end
示例输出:
user system total real
Array- 0.180000 0.000000 0.180000 ( 0.187512)
Array-ewo 0.200000 0.000000 0.200000 ( 0.194663)
hash 0.250000 0.010000 0.260000 ( 0.253355)
include? 3.660000 0.000000 3.660000 ( 3.666313)
京公网安备 11010802040832号 | 京ICP备19059560号-6 