сделать это проще, так будет быстрее

Question

Я новичок и у меня возникла проблема с упражнением. Я решил это, работает, но это слишком медленно, когда дело доходит до проверки большего числа чисел - максимальная длина приблизительно = 1.000.000. Как это могло быть написано для более быстрого решения?

def find_dups_miss(arr)
    ((arr.sort.first..arr.sort.last).to_a - arr.sort)  + [arr.select{|item| arr.count(item) > 1}.uniq.sort]
end

Тестирование:

arr1 = [10,9,8,9,6,1,2,4,3,2,5,5,3]
    Test.assert_equals(find_dups_miss(arr1),[7, [2, 3, 5, 9]])

Нужно найти пропущенный номер и дубликаты.

сообщение об ошибке: Почему мой код истек? Наши серверы настроены на выполнение кода только в течение определенного времени. В редких случаях сервер может выполнять слишком много работы и просто не может выполнить ваш код достаточно эффективно. Хотя большую часть времени эта проблема вызвана неэффективными алгоритмами. Если вы видите эту ошибку несколько раз, вы должны попытаться оптимизировать свой код дальше.

Answer 1

Это примерно так быстро, как я могу решить эту проблему сейчас

def find_dups_miss(arr)
  groups = arr.group_by(&:itself) 
  arr.minmax.reduce(:upto).to_a - groups.keys << groups.select {|_,v| v.size > 1}.keys.sort
end

Пояснения основаны на опубликованном Array

Сначала мы группируем Array элементы по себе

{10=>[10], 9=>[9, 9], 8=>[8], 6=>[6], 1=>[1], 2=>[2, 2], 4=>[4], 3=>[3, 3], 5=>[5, 5]}

Затем мы создаем Enumerator из минимального и максимального (arr.minmax.reduce(:upto)) значений из Array, преобразуем его в Array (to_a) и вычитаем все keys из предыдущей группы группировка:

arr.minmax.reduce(:upto).to_a - groups.keys
#=> [7]

Затем мы собираем все числа, которые встречались более одного раза в оригинале Array: (Я отсортировал их, потому что желаемый результат был отсортирован)

groups.select {|_,v| v.size > 1}.keys.sort
#=> [2, 3, 5, 9]

и используйте Array#<<, чтобы вставить Array обратно в тот, который мы создали на предыдущем шаге, в результате

#=> [7,[2, 3, 5, 9]]

Если пропущен только один номер, то следующий текст немного быстрее, поскольку он не создает дополнительного Array и коротких замыканий на первом пропущенном номере:

def find_dups_miss(arr)
  groups = arr.group_by(&:itself) 
  [groups.select {|_,v| v.size > 1}.keys.sort].unshift(arr.minmax.reduce(:upto).find {|n| groups[n].nil?} )
end

Дополнительно для очень большого Array:

groups.collect {|k,v| k if v.size > 1 }.compact.sort 

кажется немного более эффективным, чем

groups.select {|_,v| v.size > 1}.keys.sort

Answer 2

Нам дан массив целых чисел arr со свойством, в котором он содержит каждое целое число от min_val до max_val, кроме одного, где min_val, max_val = arr.minmax. Мы хотим определить отсутствующее целое число, а также повторяющиеся значения в arr.

require 'set'

def missing_and_dups(arr)
  smallest, largest = arr.minmax
  dups = Set.new
  all = arr.each_with_object(Set.new) { |n,all| dups << n if all.add?(n).nil? }
  [(smallest+largest)*(largest-smallest+1)/2 - all.sum, dups.to_a]
end

missing_and_dups [10,9,8,9,6,1,2,4,3,2,5,5,3]
  #=> [7, [9, 2, 5, 3]]

Обратите внимание, что Set # add? возвращает nil, если добавляемый элемент уже находится в наборе. Вместо того, чтобы найти отсутствующий элемент n с помощью

((smallest..largest).to_a - arr).first

Я использовал тот факт, что

all.sum + n = (smallest+largest)*(smallest+largest-1)/2

Answer 3

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

def find_dups_missing(arr)
  min, max = arr.min, arr.max
  hash = {}
  min.upto(max) { |i| hash[i] = :sentinel }
  arr.each { |el| hash[el] == :sentinel ? hash[el] = 1 : hash[el] += 1 }

  hash.select { |_, v| v == :sentinel }.keys << hash.select { |_, v| v != :sentinel && v > 1 }.keys
end

Мы перебираем, строим хеш, где каждый ключ - это число от min до max, а значение указывает на объект, который является просто заполнителем (я назвал его sentinel).

Затем мы перебираем наш массив, мы спрашиваем, находится ли значение хеша все еще в своей позиции заполнителя, если это так, устанавливаем значение в 1, но если это не так, просто увеличиваем. Таким образом, мы отслеживаем, когда мы видим значение в первый раз по сравнению с последующим временем (т. Е. Дублирует).

Затем, после того как все сказано, сделано, у нас есть хеш, который выглядит так:

{1=>1, 2=>2, 3=>2, 4=>1, 5=>2, 6=>1, 7=>:sentinel, 8=>1, 9=>2, 10=>1}

Мы знаем, где значение > 1, у нас есть дубликаты, и мы также знаем, где значение все еще говорит: sentinel мы никогда не видели его в нашем массиве, есть наш пробел (ы).

Все вместе, этот метод выполняется в O(n) времени (в среднем) с O(n) пробелом.