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)

score 6 · Accepted Answer · answered Jan 24 '17 at 21:58

6

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.

answered Jan 24 '17 at 21:58

Eric Duminil

52,989
9
71
124

Cool! You can even shorten this as `map(:-@)` though I'm not sure how many people know the proper name of the negation method :) – akuhn Jan 24 '17 at 22:41
That's what rubocop converted it to, but you're right, it might not be very readable. To be honest, I've never seen it or use it before. Do you know why `@` is used? – Eric Duminil Jan 24 '17 at 22:44
To distinguish the unary `-a` from the binary `a - b` operator, not sure though why an `@` symbol is used. Guess Matz just made something up. Same for `+@` and `~@` but not for `!` which always confuses me. – akuhn Jan 24 '17 at 22:46
Thanks for the comment. What's the point of `+@`? And what's `~@`? SO is great, I really learn a lot every day! – Eric Duminil Jan 24 '17 at 22:48
1

Actually, I stand corrected. Ruby accepts `def !@; end` and `def ~@; end` but their names will be just `!` and `~`. Tilde is a binary operator that flips all bits in a number, the so called 2's complement. You can use `-` and `+` to freeze and unfreeze strings. – akuhn Jan 24 '17 at 22:53
2

`array - array.select(&0.method(:<)).map(&:-@)` :) /cc @akuhn – Aleksei Matiushkin Jan 26 '17 at 19:29
@mudasobwa hahaha! +1 for smiley-style coding! – akuhn Jan 26 '17 at 21:06

score 5 · Answer 2 · edited May 23 '17 at 12:10

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)

`Array#-` creates a hash too, but does so internally in native code hence it is faster by a constant factor but likely has the same `O(n)` complexity. — akuhn, Jan 24 '17 at 23:29
@akuhn good point, builtins are almost always faster than interpreted code, even with possibly equivalent big-Oh performance. — maerics, Jan 24 '17 at 23:32
Being a variant of `Array-`, I expected my solution would have similar performance. It's about 12% faster with your benchmark. — Cary Swoveland, Jan 25 '17 at 02:23
Thanks for the benchmark! `rand(100) * (rand < 0.5 ? 1 : -1)` is just `rand(-99..99)` BTW. — Eric Duminil, Jan 25 '17 at 09:13
@CarySwoveland I've added it to the benchmark above, thanks. — maerics, Jan 25 '17 at 15:44
@maerics: No problem. I think that your `rand` variant is returning twice as many `0`s than `1`s, BTW. — Eric Duminil, Jan 25 '17 at 17:21

moveson · Answer 3 · 2017-02-27T20:36:29.570

You can do this easily using Array#reject:

>> a = [1, 5, 10, 5, -5, -1, 9]
>> a.reject { |e| e < 0 && a.include?(e.abs) }
=> [1, 5, 10, 5, 9]

To clarify with another example, this will not remove negative values that do not have a corresponding positive value in the array:

>> b = [1, 5, 10, 5, -5, -1, 9, -15]
>> b.reject { |e| e < 0 && b.include?(e.abs) }
=> [1, 5, 10, 5, 9, -15]

You can define a method like so:

def reject_negative_duplicates(array)
  array.reject { |e| e < 0 && array.include?(e.abs) }
end

>> reject_negative_duplicates(a)
=> [1, 5, 10, 5, 9]
>> reject_negative_duplicates(b)
=> [1, 5, 10, 5, 9, -15]

Or extend (monkey patch) Array:

class Array
  def reject_negative_duplicates
    self.reject { |e| e < 0 && self.include?(e.abs) }
  end
end

>> a.reject_negative_duplicates
=> [1, 5, 10, 5, 9]
>> b.reject_negative_duplicates
=> [1, 5, 10, 5, 9, -15]

Very readable solution. It's O(n^2) so you could speed it up by putting the original array in a `Set` for the `include` look ups to be O(1). — Anthony, Jan 24 '17 at 19:55
`self.` is not needed in the definition of the `Array` method, but I know some people like to include it anyway. — Cary Swoveland, Jan 25 '17 at 08:20

score 3 · Answer 4 · answered Jan 25 '17 at 02:10

3

arr = [1, 5, 10, 0, 5, -5, -1, 9, -4]

arr - arr.each_with_object([]) { |n,b| b << -n if n > 0 }
  #=> [1, 5, 10, 0, 5, 9, -4]

answered Jan 25 '17 at 02:10

Cary Swoveland

106,649
6
63
100

I see this is but a minor variant of @Eric's solution. – Cary Swoveland Jan 25 '17 at 02:13

score 0 · Answer 5 · edited May 23 '17 at 11:46

0

In Ruby you could use the uniq method: https://ruby-doc.org/core-2.2.0/Array.html#method-i-uniq.

Otherwise, you'll want to check an answer like this one which covers how to build a structure to iterate through an array.

edited May 23 '17 at 11:46

Community

1
1

answered Jan 24 '17 at 19:40

CJ Johnson

1,081
9
13

How would you apply `uniq` to the example given in the question? – Sagar Pandya Jan 24 '17 at 19:50
CJ, best provide a code example with your answer. It is best practice on Stakcoverflow to provide examples in addition to links to documentation. – akuhn Jan 24 '17 at 19:51
duplicates for positive integers are allowed so this doesn't work. – Anthony Jan 24 '17 at 19:53
Also : `[-3]` is converted to `[3]` – Eric Duminil Jan 24 '17 at 22:56

How to delete negative duplicates from an array?

5 Answers5