scala - 如何高效/优雅地提取连续整数的范围？

Question

让我们从一个整数序列开始，例如:

val seq = List(1,2,3,4,5,6,9,10,11,14,15,16,18)

我想获得代表连续集合的一系列对，例如:

val ranges = List(1,6,9,11,14,16,18,18)

替代格式Seq[(Int,Int)]也是可以接受的:

val ranges = List((1,6),(9,11),(14,16),(18,18))

说明: - 1..6 和 11..16 范围内的整数位于 seq 中 - 整数 18 位于 seq 中，但没有后继或前趋，因此它在 ranges 中显示为 18,18 >

请注意，单元素序列应始终成对报告，例如:

val seq = List(18, 19, 21)

应该给出结果:

val ranges = List(18,19,21,21)

或者，如果您更喜欢 Tuple2 风格:

val ranges = List((18,19),(21,21))

我想要一个从 seq 派生 ranges 的函数；解决方案(由同事提供)是:

def toRanges(a: Seq[Int]): Seq[Int] = {
  val min = a.map(x => (x, a contains x - 1)).filter(!_._2).map(_._1)
  val max = a.map(x => (x, a contains x + 1)).filter(!_._2).map(_._1)
  return (min ++ max).sorted
}

这确实很优雅，但由于使用了 contains，我不确定效率。

任何人都可以在效率或优雅方面提供更好的解决方案吗？

谢谢!

Answer 1

如果输入是有序的(或者您愿意先对其进行排序)，您可以使用 foldLeft 在一次传递中非常简洁地完成此操作(好吧，使用 reverse 进行两次传递，但这是使用列表的一个工件，如果您愿意放弃一些优雅，则可以避免):

seq.foldLeft[List[(Int, Int)]](Nil) {
  case ((a, b) :: rest, i) if i == b + 1 => (a, i) :: rest
  case (acc, i) => (i, i) :: acc
}.reverse

在这种情况下，我们得到以下结果:

res0: List[(Int, Int)] = List((1,6), (9,11), (14,16), (18,18))

对于每个元素，我们检查它是否是我们添加的最后一个范围末尾的后继元素。如果是，我们替换该范围内的末尾。如果不是，我们开始一个新的范围。