Ruby: Как найти и вернуть дублирующее значение в массиве?

Ответ 1

a = ["A", "B", "C", "B", "A"]
a.detect{ |e| a.count(e) > 1 }

UPDATE

Я знаю, что это не очень элегантный ответ, но мне это нравится. Это красивый код лайнера. И работает отлично, если вам не нужно обрабатывать огромный набор данных.

Ищете более быстрое решение? вот, пожалуйста!

def find_one_using_hash_map(array)
  map = {}
  dup = nil
  array.each do |v|
    map[v] = (map[v] || 0 ) + 1

    if map[v] > 1
      dup = v
      break
    end
  end

  return dup
end

Линейный, O (n), но теперь нужно управлять несколькими LOC, нужны тестовые случаи и прочее!

Если вам нужно еще более быстрое решение, попробуйте вместо этого C :)

А вот гиты, сравнивающие разные решения: https://gist.github.com/naveed-ahmad/8f0b926ffccf5fbd206a1cc58ce9743e

Ответ 2

Вы можете сделать это несколькими способами, причем первый вариант будет самым быстрым:

ary = ["A", "B", "C", "B", "A"]

ary.group_by{ |e| e }.select { |k, v| v.size > 1 }.map(&:first)

ary.sort.chunk{ |e| e }.select { |e, chunk| chunk.size > 1 }.map(&:first)

И опция O (N ^ 2) (т.е. менее эффективная):

ary.select{ |e| ary.count(e) > 1 }.uniq

Ответ 3

Просто найдите первый экземпляр, где индекс объекта (подсчет слева) не совпадает с индексом объекта (считая справа).

arr.detect {|e| arr.rindex(e) != arr.index(e) }

Если дубликатов нет, возвращаемое значение будет равно нулю.

Я считаю, что это самое быстрое решение, размещенное в потоке до сих пор, так как оно не зависит от создания дополнительных объектов, а #index и #rindex реализованы в C. Большой-O время работы N ^ 2 и, следовательно, медленнее, чем у Sergio's, но время стены может быть намного быстрее из-за того, что "медленные" части работают в C.

Ответ 4

detect находит только один дубликат. find_all найдет их все:

a = ["A", "B", "C", "B", "A"]
a.find_all { |e| a.count(e) > 1 }

Ответ 5

Вот еще два способа найти дубликат.

Используйте набор

require 'set'

def find_a_dup_using_set(arr)
  s = Set.new
  arr.find { |e| !s.add?(e) }
end

find_a_dup_using_set arr
  #=> "hello" 

Используйте select вместо find чтобы вернуть массив всех дубликатов.

Используйте Array#difference

class Array
  def difference(other)
    h = other.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
    reject { |e| h[e] > 0 && h[e] -= 1 }
  end
end

def find_a_dup_using_difference(arr)
  arr.difference(arr.uniq).first
end

find_a_dup_using_difference arr
  #=> "hello" 

.first чтобы вернуть массив всех дубликатов.

Оба метода возвращают nil если нет дубликатов.

Я предложил добавить Array#difference к ядру Ruby. Больше информации в моем ответе здесь.

эталонный тест

Давайте сравним предложенные методы. Во-первых, нам нужен массив для тестирования:

CAPS = ('AAA'..'ZZZ').to_a.first(10_000)
def test_array(nelements, ndups)
  arr = CAPS[0, nelements-ndups]
  arr = arr.concat(arr[0,ndups]).shuffle
end

и метод для запуска тестов для разных тестовых массивов:

require 'fruity'

def benchmark(nelements, ndups)
  arr = test_array nelements, ndups
  puts "\n#{ndups} duplicates\n"    
  compare(
    Naveed:    -> {arr.detect{|e| arr.count(e) > 1}},
    Sergio:    -> {(arr.inject(Hash.new(0)) {|h,e| h[e] += 1; h}.find {|k,v| v > 1} ||
                     [nil]).first },
    Ryan:      -> {(arr.group_by{|e| e}.find {|k,v| v.size > 1} ||
                     [nil]).first},
    Chris:     -> {arr.detect {|e| arr.rindex(e) != arr.index(e)} },
    Cary_set:  -> {find_a_dup_using_set(arr)},
    Cary_diff: -> {find_a_dup_using_difference(arr)}
  )
end

Я не включил ответ @JjP, потому что должен быть возвращен только один дубликат, и когда его/ее ответ изменяется, чтобы он соответствовал предыдущему ответу @Naveed. Я также не включил ответ @Marin, который, хотя и был опубликован до ответа @Naveed, возвращал все дубликаты, а не только один (незначительный момент, но нет смысла оценивать оба, так как они идентичны, когда возвращают только один дубликат).

Я также изменил другие ответы, которые возвращали все дубликаты, чтобы вернуть только первый найденный, но это не должно существенно повлиять на производительность, так как они вычислили все дубликаты перед выбором одного.

Результаты для каждого теста перечислены от самого быстрого до самого медленного:

Сначала предположим, что массив содержит 100 элементов:

benchmark(100, 0)
0 duplicates
Running each test 64 times. Test will take about 2 seconds.
Cary_set is similar to Cary_diff
Cary_diff is similar to Ryan
Ryan is similar to Sergio
Sergio is faster than Chris by 4x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(100, 1)
1 duplicates
Running each test 128 times. Test will take about 2 seconds.
Cary_set is similar to Cary_diff
Cary_diff is faster than Ryan by 2x ± 1.0
Ryan is similar to Sergio
Sergio is faster than Chris by 2x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(100, 10)
10 duplicates
Running each test 1024 times. Test will take about 3 seconds.
Chris is faster than Naveed by 2x ± 1.0
Naveed is faster than Cary_diff by 2x ± 1.0 (results differ: AAC vs AAF)
Cary_diff is similar to Cary_set
Cary_set is faster than Sergio by 3x ± 1.0 (results differ: AAF vs AAC)
Sergio is similar to Ryan

Теперь рассмотрим массив с 10000 элементов:

benchmark(10000, 0)
0 duplicates
Running each test once. Test will take about 4 minutes.
Ryan is similar to Sergio
Sergio is similar to Cary_set
Cary_set is similar to Cary_diff
Cary_diff is faster than Chris by 400x ± 100.0
Chris is faster than Naveed by 3x ± 0.1

benchmark(10000, 1)
1 duplicates
Running each test once. Test will take about 1 second.
Cary_set is similar to Cary_diff
Cary_diff is similar to Sergio
Sergio is similar to Ryan
Ryan is faster than Chris by 2x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(10000, 10)
10 duplicates
Running each test once. Test will take about 11 seconds.
Cary_set is similar to Cary_diff
Cary_diff is faster than Sergio by 3x ± 1.0 (results differ: AAE vs AAA)
Sergio is similar to Ryan
Ryan is faster than Chris by 20x ± 10.0
Chris is faster than Naveed by 3x ± 1.0

benchmark(10000, 100)
100 duplicates
Cary_set is similar to Cary_diff
Cary_diff is faster than Sergio by 11x ± 10.0 (results differ: ADG vs ACL)
Sergio is similar to Ryan
Ryan is similar to Chris
Chris is faster than Naveed by 3x ± 1.0

Обратите внимание, что find_a_dup_using_difference(arr) была бы намного более эффективной, если бы Array#difference была реализована в C, что было бы в случае добавления в ядро Ruby.

Заключение

Многие из ответов являются разумными, но использование набора является лучшим выбором. Он самый быстрый в случаях средней сложности, самый быстрый в самых сложных и только в вычислительно тривиальных случаях - когда ваш выбор все равно не имеет значения - его можно победить.

Один очень особый случай, в котором вы можете выбрать решение Криса, будет, если вы захотите использовать метод для раздельной дедупликации тысяч небольших массивов и ожидать, что дубликат будет найден, как правило, менее чем в 10 элементах. Это будет немного быстрее поскольку это позволяет избежать небольших дополнительных затрат на создание набора.

Ответ 6

Увы, большинство ответов O(n^2).

Вот решение O(n),

a = %w{the quick brown fox jumps over the lazy dog}
h = Hash.new(0)
a.find { |each| (h[each] += 1) == 2 } # => 'the"

В чем сложность этого?

• Запускается в O(n) и разбивается на первое совпадение
• Использует память O(n), но только минимальное количество

Теперь, в зависимости от того, насколько часто повторяются дубликаты в вашем массиве, эти среды выполнения могут стать еще лучше. Например, если массив размера O(n) был отбирается из совокупности k << n разных элементов, только сложность как для среды выполнения, так и для пространства становится O(k), однако более вероятно, что исходный плакат проверяет ввод и хочет убедитесь, что дубликатов нет. В этом случае как время выполнения, так и память O(n), так как мы ожидаем, что элементы не будут иметь повторений для большинства входов.

Ответ 7

Объекты Ruby Array имеют отличный метод, select.

select {|item| block } → new_ary
select → an_enumerator

Здесь вас интересует первая форма. Он позволяет выбирать объекты, которые проходят тест.

Объекты Ruby Array имеют другой метод count.

count → int
count(obj) → int
count { |item| block } → int

В этом случае вас интересуют дубликаты (объекты, которые появляются более одного раза в массиве). Соответствующий тест a.count(obj) > 1.

Если a = ["A", "B", "C", "B", "A"], то

a.select{|item| a.count(item) > 1}.uniq
=> ["A", "B"]

Вы заявляете, что хотите только один объект. Поэтому выберите один.

Ответ 8

Что-то вроде этого будет работать

arr = ["A", "B", "C", "B", "A"]
arr.inject(Hash.new(0)) { |h,e| h[e] += 1; h }.
    select { |k,v| v > 1 }.
    collect { |x| x.first }

То есть, поместите все значения в хэш, где ключ - это элемент массива, а значение - количество вхождений. Затем выберите все элементы, которые встречаются более одного раза. Легко.

Ответ 9

Я знаю, что эта тема касается Ruby специально, но я приземлился здесь, ища, как это сделать в контексте Ruby on Rails с ActiveRecord, и подумал, что я тоже поделюсь своим решением.

class ActiveRecordClass < ActiveRecord::Base
  #has two columns, a primary key (id) and an email_address (string)
end

ActiveRecordClass.group(:email_address).having("count(*) > 1").count.keys

Вышеприведенный массив возвращает все адреса электронной почты, которые дублируются в этой таблице базы данных примеров (в Rails будет "active_record_classes" ).

Ответ 10

find_all() возвращает array, содержащий все элементы enum, для которых block не false.

Чтобы получить элементы duplicate

>> arr = ["A", "B", "C", "B", "A"]
>> arr.find_all { |x| arr.count(x) > 1 }

=> ["A", "B", "B", "A"]

Или дублировать элементы uniq

>> arr.find_all { |x| arr.count(x) > 1 }.uniq
=> ["A", "B"] 

Ответ 11

a = ["A", "B", "C", "B", "A"]
a.each_with_object(Hash.new(0)) {|i,hash| hash[i] += 1}.select{|_, count| count > 1}.keys

Это процедура O(n).

В качестве альтернативы вы можете выполнить одну из следующих строк. Также O (n), но только одна итерация

a.each_with_object(Hash.new(0).merge dup: []){|x,h| h[:dup] << x if (h[x] += 1) == 2}[:dup]

a.inject(Hash.new(0).merge dup: []){|h,x| h[:dup] << x if (h[x] += 1) == 2;h}[:dup]

Ответ 12

Вот мой пример на большом наборе данных - например, в старой таблице dBase, чтобы найти повторяющиеся части.

# Assuming ps is an array of 20000 part numbers & we want to find duplicates
# actually had to it recently.
# having a result hash with part number and number of times part is 
# duplicated is much more convenient in the real world application
# Takes about 6  seconds to run on my data set
# - not too bad for an export script handling 20000 parts

h = {};

# or for readability

h = {} # result hash
ps.select{ |e| 
  ct = ps.count(e) 
  h[e] = ct if ct > 1
}; nil # so that the huge result of select doesn't print in the console

Ответ 13

r = [1, 2, 3, 5, 1, 2, 3, 1, 2, 1]

r.group_by(&:itself).map { |k, v| v.size > 1 ? [k] + [v.size] : nil }.compact.sort_by(&:last).map(&:first)

Ответ 14

Если вы сравниваете два различных массивов (вместо одного против себя) очень быстрый способ заключается в использовании оператора пересекаться & обеспечиваются рубиновым классом Array,.

# Given
a = ['a', 'b', 'c', 'd']
b = ['e', 'f', 'c', 'd']

# Then this...
a & b # => ['c', 'd']

Ответ 15

each_with_object - твой друг!

input = [:bla,:blubb,:bleh,:bla,:bleh,:bla,:blubb,:brrr]

# to get the counts of the elements in the array:
> input.each_with_object({}){|x,h| h[x] ||= 0; h[x] += 1}
=> {:bla=>3, :blubb=>2, :bleh=>2, :brrr=>1}

# to get only the counts of the non-unique elements in the array:
> input.each_with_object({}){|x,h| h[x] ||= 0; h[x] += 1}.reject{|k,v| v < 2}
=> {:bla=>3, :blubb=>2, :bleh=>2}

Ответ 16

a = ["A", "B", "C", "B", "A"]
b = a.select {|e| a.count(e) > 1}.uniq
c = a - b
d = b + c

Результаты

 d
=> ["A", "B", "C"]

Ответ 17

Мне нужно было выяснить, сколько было дубликатов и чем они были, поэтому я написал функциональное построение на основе того, что Навид опубликовал ранее:

def print_duplicates(array)
  puts "Array count: #{array.count}"
  map = {}
  total_dups = 0
  array.each do |v|
    map[v] = (map[v] || 0 ) + 1
  end

  map.each do |k, v|
    if v != 1
      puts "#{k} appears #{v} times"
      total_dups += 1
    end
  end
  puts "Total items that are duplicated: #{total_dups}"
end

Ответ 18

def duplication given_array
  duplicate_array = []
  given_array.each_with_index do |num, index| 
    0.upto(given_array.length) do |ind|
      unless (ind) == index
        if (given_array[ind] == given_array[index]) && !duplicate_array.include?(given_array[ind])
          duplicate_array << given_array[ind]
        end 
      end
    end
  end
  duplicate_array
end

result = duplication ["A", "B", "C", "B", "A"]

ставит результат

Ответ 19

def firstRepeatedWord(string)
  h_data = Hash.new(0)
  string.split(" ").each{|x| h_data[x] +=1}
  h_data.key(h_data.values.max)
end

Ответ 20

[1,2,3].uniq!.nil? => true [1,2,3].uniq!.nil? => true [1,2,3,3].uniq!.nil? => false [1,2,3,3].uniq!.nil? => false

Обратите внимание, что вышесказанное является разрушительным