Подсчитайте, сколько раз числа из списка встречаются в списке перебранных интервалов в Scala

Question

Скажите, у меня есть список кортежей:

 val ranges= List((1,4), (5,8), (9,10))

и список номеров

val nums = List(2,2,3,7,8,9)

Я хочу сделать карту из кортежа в диапазонах, сколько раз данное число из чисел попадает в интервал этого кортежа.

Выход:

Map ((1,4) -> 3, (5,8) -> 2, (9,10) -> 1)

Как лучше всего это делать в Scala

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

С наилучшими пожеланиями

Answer 1

Вот эффективное однопроходное решение:

ranges
  .map(r => r -> nums.count(n => n >= r._1 && n <= r._2))
  .toMap

Это позволяет избежать затрат на создание списка чисел, а затем сжать их с диапазонами на отдельном шаге.

Это версия, в которой используется больше функций Scala, но она слишком причудлива:

(for {
  r <- ranges
  range = r._1 to r._2
} yield r -> nums.count(range.contains)
).toMap

Это также менее эффективно, потому что contains должен учитывать диапазоны со значением шага и поэтому является более сложным.

---

А вот еще более эффективная версия, позволяющая избежать любых временных структур данных:

val result: Map[(Int, Int), Int] =
  ranges.map(r => r -> nums.count(n => n >= r._1 && n <= r._2))(collection.breakOut)

См. Это объяснение breakOut, если вы не знакомы с ним. Использование breakOut означает, что вызов map создаст Map напрямую, а не List, который должен быть преобразован в Map с использованием toMap.

Answer 2

Примерно так:

val ranges = List((1, 4), (5, 8), (9, 10))
val nums = List(2, 2, 3, 7, 8, 9)

val occurences = ranges.map { case (l, r) => nums.count((l to r) contains _) }
val map = (ranges zip occurences).toMap

println(map) // Map((1,4) -> 3, (5,8) -> 2, (9,10) -> 1)

В основном сначала рассчитывается количество вхождений, [3, 2, 1]. Оттуда легко построить карту. И как он рассчитывает вхождения:

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

РЕДАКТИРОВАТЬ: Не уверен, почему этот ответ получает отрицательный голос, возможно, я как-то неправильно понял вопрос.