-1

输入是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)会丢失一些元素。我想知道有没有一种 Scala 集合 API 或方法可以用来解决这个难题？另外，如果可能的话，我更喜欢功能更强大。

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

提前致谢。

4

3 回答 3

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))
于 2018-05-09T04:21:49.087 回答
1

你可以试试这个功能。它也适用于大量列表

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))

如果您还有任何疑问，请告诉我。我很乐意澄清它们。

于 2018-05-09T03:24:08.110 回答
1

Here is a recursive solution for your reference:

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))
于 2018-05-09T04:40:12.053 回答