У меня есть массив типа [1,1,1,2,4,6,3,3], и я хотел бы получить список повторяющихся элементов, в данном случае [1,3]. Я написал это:
my_array.select{|obj|my_array.count(obj)>1}.uniq
Но это трагически неэффективно (o(n²)). У вас есть идея получше? Если можно кратко.
Спасибо
Вдохновленный ответом Ильи Хайкинсона:
def repeated(array)
counts = Hash.new(0)
array.each{|val|counts[val]+=1}
counts.reject{|val,count|count==1}.keys
end
array.inject(Hash.new(0)) { |h, i| h[i] += 1; h }.reject { |v, c| c == 1 }.keys
- person Marek Příhoda; 11.12.2011
detect, find_all и т. д.
- person rapcal; 18.12.2015
Set.new. Он использует хэш под капотом и отлично подходит, когда вам нужен доступ к хеш-ключу O (1), но с простотой массива. Кроме того, это способствует удобочитаемости, поскольку вся логика сводится к прекрасному очевидному dups.add(val) if seen_already.include?(val).
- person Adamantish; 10.01.2019
Используя библиотеку Ruby Set:
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]
Я считаю, что это должно быть O (n), потому что Set#add и Set#add? Насколько я знаю, это операции с постоянным временем.
Как насчет чего-то подобного? Он будет работать за 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
Решение O(n) (измените << x на + [x] и update на merge, чтобы сделать его полностью функциональным):
rs = xs.inject([[], {}]) do |(out, seen), x|
[(seen[x] == 1 ? (out << x) : out), seen.update(x => (seen[x] || 0)+1)]
end[0]
Гораздо более простой, но менее эффективный подход:
rs = xs.group_by { |x| x }.select { |y, ys| ys.size > 1 }.keys
Та же идея, избегающая промежуточного хеша с использованием «понимания списка»:
rs = xs.group_by { |x| x }.map { |y, ys| y if ys.size > 1 }.compact
xs = [1,1,1].
- person Jan; 10.12.2011
Использование inject
[1,1,1,2,4,6,3,3].inject({}){ |ele, n| ele[n] = nil; ele }.keys
# => [1, 2, 4, 6, 3]
ele инициализируется {}, на каждой итерации к хэшу ele добавляется ключ с номером n и значением nil. В конце ele возвращается как:
{1=>nil, 2=>nil, 4=>nil, 6=>nil, 3=>nil}
Нам нужны только ключи, поэтому .keys заканчивает работу.
Некоторые идеи: вам нужно будет выяснить правильные структуры данных библиотеки:
1 Отсортируйте массив O(nlogn), затем просмотрите массив
2 Создайте набор, найдите текущий элемент массива в наборе и, если он не найден, вставьте и продолжите для всех элементов -- снова O(nlogn).
Я думал о том, чтобы подсчитать, сколько раз уникальный элемент появляется в массиве. Это может быть действительно неэффективно, как и первоначальное предложение, но было весело смотреть на проблему. Я не проводил никаких тестов на больших массивах, так что это просто упражнение.
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]
Это будет работать, если дублированные записи всегда идут подряд, как в вашем примере; в противном случае вам пришлось бы сначала сортировать. each_cons исследует скользящее окно указанного размера.
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
