How to delete negative duplicates from an array?

Question

How can I effectively delete negative duplicates of positive integers from an array of positive and negative integers like this: [1, 5, 10, 5, -5, -1, 9] as a result, I want to have: [1, 5, 10, 5, 9] (-1 and -5 removed as they are negative duplicates of 1 and 5)

Answer 1

This is the easiest method I could find :

• select positive numbers
• calculate their opposite number
• remove them from the original array

---

array = [1, 5, 10, 5, -5, -1, 9]

p array - array.select{ |i| i > 0 }.map{ |i| -i }
# [1, 5, 10, 5, 9]

It uses Array#-, which should be reasonably fast.

Answer 2

You can do this in O(n) with just two passes through the array by hashing the positive numbers then rejecting from the array negative values whose abs was hashed:

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

Note interestingly that the Array- solutions are considerably faster than others listed so far:

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

Example output:

                      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)