Как объединить списки, которые содержат рекурсивный общий атрибут

Question

Ввод List(1,2), List(3,4), List(1000), List(5,6), List(100, 1,3), List(99, 4, 5).

Ожидаемый результат: List(1,2,3,4,5,6,99,100), List(1000)

Я пытаюсь использовать foldLeft, но обнаруживаю, что в одном цикле O(n) не хватает некоторых элементов. Интересно, есть ли какой-нибудь API-интерфейс или метод Scala collection, который я могу использовать для решения этой головоломки? Кроме того, я предпочитаю быть более функциональным, если это возможно.

def merge(lists: List[List[Int]]): List[List[Int]] = {
   ???
}

Заранее спасибо.

Answer 1

Все, что вам нужно, это filter, toSet и sorted вызовы функций как

def merge(lists: List[List[Int]]): List[List[Int]] = {
  val flattenedList = lists.flatten
  val repeatedList = lists.filter(list => list.map(x => flattenedList.count(_ == x) > 1).contains(true))
  val notRepeatedList = lists.diff(repeatedList)
  List(repeatedList.flatten.toSet.toList.sorted) ++ notRepeatedList
}

и затем вызов функции merge как

val lists = List(List(1,2), List(3,4), List(1000), List(5,6), List(100, 1,3), List(99, 4, 5))

println(merge(lists))

даст вам

List(List(1, 2, 3, 4, 5, 6, 99, 100), List(1000))

Answer 2

Вот рекурсивное решение для вашей справки:

def merge(a:List[List[Int]]):List[List[Int]] = {
  a match {
    case Nil => Nil
    case h::l =>
    l.partition(_.intersect(h)!=Nil) match {
      case (Nil, _) =>
      //No intersect, just merge the rest and add this one
      h::merge(l)
      case (intersects, others) =>
      //It has intersects, merge them to one list and continue merging
      merge((h::intersects).flatten.distinct::others)
    }
  }
}
res9: List[List[Int]] = List(List(1, 2, 100, 3, 4, 99, 5, 6), List(1000))

Answer 3

Вы можете попробовать эту функцию.Он хорошо работает и с огромными списками

def merge(input: List[List[Int]]): List[List[Int]] = {

  val sets: Set[Set[Int]] = input.map(_.toSet).toSet

  def hasIntersect(set: Set[Int]): Boolean =
    sets.count(set.intersect(_).nonEmpty) > 1

  val (merged, rejected) = sets partition hasIntersect
  List(merged.flatten, rejected.flatten).map(_.toList.sorted)
}

merge(List(List(1, 2), List(3, 4), List(1000), List(5, 6), List(100, 1, 3), List(99, 4, 5)))

Вы получите результат в формате

res0: List[List[Int]] = List(List(1, 2, 3, 4, 5, 6, 99, 100), List(1000))

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