Scala中按指定分割点拆分List集合的实现方法
Scala List按指定分割点拆分实现方案
基础实现(代码简洁,适合常规规模列表)
利用Scala集合内置方法实现两次线性遍历,逻辑清晰易维护:
def splitListAtTarget[T](list: List[T], target: T): List[List[T]] = { val targetIndex = list.indexOf(target) // 未找到分割点时返回原列表+空列表 if (targetIndex == -1) List(list, Nil) // 拆分位置为分割索引+2,确保包含分割元素及紧随的下一个元素,匹配示例预期 else list.splitAt(targetIndex + 2) match { case (left, right) => List(left, right) } }
测试示例输入:
val input = List(2,6,4,7,9,10) splitListAtTarget(input, 4) // 输出:List(List(2, 6, 4, 7), List(9, 10)) 完全匹配预期
高效实现(单次遍历,适合超大列表)
用尾递归实现仅一次遍历完成定位和拆分,避免重复遍历的性能损耗,同时优化List追加操作的开销:
import scala.annotation.tailrec def splitListAtTargetEfficient[T](list: List[T], target: T): List[List[T]] = { @tailrec def loop(remaining: List[T], prefixReversed: List[T]): (List[T], List[T]) = remaining match { case Nil => (prefixReversed.reverse, Nil) // 匹配到分割元素 case h :: t if h == target => t match { // 分割元素在列表末尾的边界处理 case Nil => ((h :: prefixReversed).reverse, Nil) // 包含紧随的下一个元素到前半段,剩余元素为后半段 case next :: rest => ((next :: h :: prefixReversed).reverse, rest) } // 未匹配到分割元素,继续遍历 case h :: t => loop(t, h :: prefixReversed) } val (left, right) = loop(list, Nil) List(left, right) }
测试同示例输入,输出与基础实现完全一致。
常见需求调整
- 若需要拆分后仅包含分割元素本身(前半段到分割点为止,后半段为剩余元素):基础实现把
splitAt参数改为targetIndex + 1,尾递归实现匹配到分割点后直接返回((h :: prefixReversed).reverse, t)即可,示例输入会输出List(List(2,6,4), List(7,9,10))。 - 若需要匹配最后一个出现的分割点而非第一个:基础实现把
indexOf替换为lastIndexOf即可,尾递归实现调整为从后向前遍历或遍历完所有匹配点后再确定拆分位置。 - 若需要自定义分割条件(如按元素大小、类型等拆分):把尾递归里的
h == target替换为对应的判断函数即可,灵活性更高。
内容的提问来源于stack exchange,提问作者isopl
相关产品推荐
相关产品推荐

