How can I efficiently extract repeated elements in a Ruby array?

Question

I have an array like [1,1,1,2,4,6,3,3] and I would like to get the list of repeated elements, in this case [1,3]. I wrote this:

my_array.select{|obj|my_array.count(obj)>1}.uniq

But it is tragically inefficient (o(n²)). Do you have a better idea? If possible concise.

Thanks

Answer 1

Some ideas: you'd have to figure out the correct library data structures:

1 Sort the array O(nlogn), then run through the array

2 Create a set, search for the current array element in the set and if not found, insert and proceed for all the elements -- O(nlogn) again.

Answer 2

Using Ruby's Set library:

require 'set'

ary = [1,1,1,2,4,6,3,3]
dups = Set.new
test_set = Set.new
ary.each {|val| dups.add(val) unless test_set.add?(val)}
dups.to_a # [1, 3]

I believe this should be O(n), because Set#add and Set#add? are constant-time operations, as far as I know.

Answer 3

How about something like this? It will run in O(n).

a = [1,1,1,2,4,6,3,3]
b = {}
a.each { |v| if b.has_key? v then b[v] = b[v]+1 else b[v]=1 end }
b.reject { |k,v| if v > 1 then false else true end }.keys

Answer 4

Inspired by Ilya Haykinson's answer:

def repeated(array)
  counts = Hash.new(0)
  array.each{|val|counts[val]+=1}
  counts.reject{|val,count|count==1}.keys
end

Answer 5

I was thinking of counting how many times a unique element appears in array. It may be really inefficient just like the original suggestion but it was fun looking at the problem. I didn't do any benchmarks on larger arrays so this is just an excercise.

a = [1,1,1,2,4,6,3,3]

dupes = []
a.uniq.each do |u|
  c = a.find_all {|e| e == u}.size
  dupes << [u, c] unless c == 1
end

puts dupes.inspect

# dupes = [[1, 3], [3, 2]]
# 1 appears 3 times
# 3 appears twice


# to extract just the elment a bit cleaner
dupes = a.uniq.select do |u|
  a.find_all {|e| e == u}.size != 1
end
puts dupes.inspect
# returns [1,3]

Answer 6

This will work if the duplicated entries are always consecutive, as in your example; otherwise you would have to sort first. each_cons examines a rolling window of the specified size.

require 'set'

my_array = [1,1,1,2,4,6,3,3]
dups = Set.new
my_array.each_cons(2) {|a,b| dups.add(a) if (a == b)}
p dups.to_a