list - 找到重复项时拆分列表 scala

Question

我在 Scala 中有一个元素列表，我正在寻找一种在找到重复项时拆分列表的方法。

例如:List(x,y,z,e,r,y,g,a)将转换为 List(List(x,y,z,e,r),List(y,g,a))或 List(x,y,z,x,y,z)至 List(x,y,z), List(x,y,z)和 List(x,y,z,y,g,x)至 List(x,y,z), List(y,g,x)
有没有比分别对每个元素进行迭代和检查更有效的方法？

Answer 1

此解决方案有一些注意事项:

我不是在声称“性能”，尽管我认为它比 O(n^2) 更好，这是蛮力。

这是假设您在找到重复项时进行拆分，其中“重复”表示“存在于前一个拆分中的内容”。我只检查了最后一段，就作弊了一点。原因是我认为它阐明了如何使用 foldLeft 一点，这是解决此问题的自然方式。

这里的一切都颠倒了，但保持秩序。这可以很容易地纠正，但增加了一个额外的 O(n) (累积)调用，并且实际上可能不需要(取决于你用它做什么)。

这是代码:

def partition(ls: List[String]): List[ListSet[String]] = {
  ls.foldLeft(List(ListSet.empty[String]))((partitionedLists, elem:String) => {
    if(partitionedLists.head.contains(elem)) {
      ListSet(elem) :: partitionedLists
    } else {
      (partitionedLists.head + elem) :: partitionedLists.tail
    }
  })
}

partition(List("x","y","z","e","r","y","g","a"))
// res0: List[scala.collection.immutable.ListSet[String]] = List(ListSet(r, e, z, y, x), ListSet(a, g, y))

我正在使用 ListSet获得 Set 的双重好处和订购，这适合您的用例。
foldLeft是一个函数，它接受一个累加器值(在本例中为 List(ListSet.empty[String]) )并在它通过您的集合元素时对其进行修改。如果我们像这里所做的那样将累加器构造为段列表，那么到我们完成时，它将拥有原始列表的所有有序段。