SockMerchant Challenge Ruby Array # количество не считается? - PullRequest
Новая
       7

SockMerchant Challenge Ruby Array # количество не считается?

0 голосов
/ 08 ноября 2018

Итак, я делаю вызов новичку на HackerHank, и странное поведение рубина поражает меня.

Задача: найти и посчитать, сколько пар в массиве. (пары носков)

Вот мой код. 

n = 100
ar = %w(50 49 38 49 78 36 25 96 10 67 78 58 98 8 53 1 4 7 29 6 59 93 74 3 67 47 12 85 84 40 81 85 89 70 33 66 6 9 13 67 75 42 24 73 49 28 25 5 86 53 10 44 45 35 47 11 81 10 47 16 49 79 52 89 100 36 6 57 96 18 23 71 11 99 95 12 78 19 16 64 23 77 7 19 11 5 81 43 14 27 11 63 57 62 3 56 50 9 13 45)

def sockMerchant(n, ar)
counter = 0
ar.each do |item|
  if ar.count(item) >= 2
    counter += ar.count(item)/2
    ar.delete(item)
  end
end
counter
end

print sockMerchant(n, ar)

Проблема в том, что это не считается хорошо. после запуска функции во внутреннем массиве ar все еще есть счетные пары, и я докажу это, запустив его снова.

Это еще не все. Если вы сортируете массив, он ведет себя по-другому.

это не имеет смысла для меня.

Вы можете проверить поведение по этой ссылке

https://repl.it/repls/HuskyFrighteningNaturallanguage

1 Ответ

0 голосов
/ 08 ноября 2018

Вы удаляете элементы из коллекции, перебирая ее - ожидайте, что случится что-то плохое. Короче говоря, не делайте этого, если вы не хотите, чтобы такие проблемы, см .: 

> arr = [1,2,1]
# => [1, 2, 1] 
> arr.each {|x| puts x; arr.delete(x) }
# 1
#  => [2]

Мы никогда не получим 2 в нашей итерации.

Простое решение, представляющее собой небольшой вариант вашего кода, может выглядеть следующим образом: 

def sock_merchant(ar)
  ar.uniq.sum do |item|
    ar.count(item) / 2
  end
end

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

Обратите внимание, что его сложность составляет n^2, поскольку для каждого уникального элемента n массива необходимо пройти весь массив, чтобы найти все элементы, равные n.

Альтернатива: сначала сгруппируйте все носки, затем проверьте, сколько у нас пар каждого типа: 

ar.group_by(&:itself).sum { |k,v| v.size / 2 }

Как ar.group_by(&:itself), сокращение от ar.group_by { |x| x.itself } будет перебирать массив и создавать хеш, похожий на это: 

{"50"=>["50", "50"], "49"=>["49", "49", "49", "49"], "38"=>["38"], ...}

И, вызвав sum, мы переберем его, суммируя количество найденных элементов (/2).

...