Scala递归模式匹配实现列表去重问题求助

嘿，我来帮你解决这个卡住的问题！你已经搭好了模式匹配的基本框架，思路方向是对的，就是在else分支不知道怎么把当前元素保留下来对吧？

先拆解你的逻辑：当当前元素x在剩余列表ys里存在时，你选择跳过x直接递归处理ys——这个思路没问题，相当于去掉前面的重复项，保留后面出现的那个。那当x不在ys里时，说明这个x是最后一次出现（或者唯一出现），我们只需要把它拼接到递归处理ys得到的去重列表前面就行啦！

修正后的代码（保留最后出现的重复元素） #

def removeDuplicates(xs: List[Int]): List[Int] = xs match {
  case Nil => Nil
  case x :: ys =>
    if (ys.contains(x)) {
      // 当前元素在后续列表还有重复，跳过它，继续递归处理剩余部分
      removeDuplicates(ys)
    } else {
      // 当前元素后续无重复，保留它，拼接剩余列表的去重结果
      x :: removeDuplicates(ys)
    }
}

// 测试你的输入列表
val xs = List(1,2,3,4,6,3,2,7,9,4)
println(removeDuplicates(xs)) // 输出: List(1, 6, 3, 2, 7, 9, 4)

额外补充：如果想保留第一次出现的重复元素 #

上面的逻辑是保留最后出现的重复项，如果你需要更常见的需求——保留第一次出现的元素、去掉后续重复项，那可以加个辅助函数，用集合跟踪已经见过的元素，这样效率也更高：

def removeDuplicatesKeepFirst(xs: List[Int]): List[Int] = {
  // 辅助函数，多一个参数记录已处理过的元素
  def helper(remaining: List[Int], seen: Set[Int]): List[Int] = remaining match {
    case Nil => Nil
    case x :: ys =>
      if (seen.contains(x)) {
        // 已经见过该元素，跳过，继续处理剩余列表
        helper(ys, seen)
      } else {
        // 第一次遇到该元素，保留它，将其加入已见集合后递归处理后续
        x :: helper(ys, seen + x)
      }
  }
  // 初始调用时，已见集合为空
  helper(xs, Set.empty)
}

println(removeDuplicatesKeepFirst(xs)) // 输出: List(1, 2, 3, 4, 6, 7, 9)

这样两种常见的去重场景就都覆盖到啦，你可以根据自己的需求选择对应的实现~

内容的提问来源于stack exchange，提问作者Krish