在Scala中检查线性时间中的数组内容相等性

Question

我想检查两个整数数组(target和arr(是否有相同的内容(两个数组都是无序的(。示例：Array(1,1,3,4,1,5)内容等于Array(1,1,1,5,4,3)内容。我知道排序的解决方案，我正在努力找出线性时间的解决方案。我首先通过target.groupBy(identity)获取目标阵列的配置文件，然后使用该配置文件折叠目标阵列：

def canBeEqual(target: Array[Int], arr: Array[Int]): Boolean = {
import scala.collection.mutable.Map
var profile = target.groupBy(identity).view.mapValues(_.length).toMap
var mutableProfile = Map(profile.toSeq: _*)
arr.fold(mutableProfile)((p, x) => {p(x) = p(x) - 1; p}).isEmpty 
}

我面临的问题：

1. 默认映射是不可变的，我使用可变映射重建了概要文件映射。这将如何影响性能
2. 我收到以下编译错误：

Line 5: error: value update is not a member of Any (in solution.scala)
arr.fold(mutableProfile)((p, x) => {p(x) = p(x) - 1; p}).isEmpty
^

我添加了类型arr.fold(mutableProfile)((p:Map[Int,Int], x:Int) => {p(x) = p(x) - 1; p}).isEmpty，但它失败了，出现了以下错误：

Line 5: error: type mismatch; (in solution.scala)
found   : (scala.collection.mutable.Map[Int,Int], Int) => scala.collection.mutable.Map[Int,Int]
required: (Any, Any) => Any

我目前被困在这一点上。无法解决类型不匹配的问题。此外，对于如何习惯地(有效地(处理这个问题的任何建议都将不胜感激。

• 免责声明1：我是Scala的初学者。上周开始阅读有关Scala的文章
• 免责声明2：以上问题为leetcode问题#1460

Answer 1

不是通过算法修改，而是为了清除编译错误：

def canBeEqual(target: Array[Int], arr: Array[Int]): Boolean = {
if (target.length != arr.length) {
false
} else {
var profile = target.groupBy(identity).mapValues(_.length)

arr.forall(x =>
profile.get(x) match {
case Some(e) if e >= 1 =>
profile += (x -> (e - 1))
true
case Some(_) => false
case None => false
})
}
}

请注意，添加或删除不可变的HashMap需要恒定的时间。(参考：https://docs.scala-lang.org/overviews/collections/performance-characteristics.html)

CCD_ 5优先于CCD_ 6，因为当条件不匹配时。(尝试将打印语句放入匹配中以验证(

或者你可以做：

target.groupBy(identity).mapValues(_.length) == arr.groupBy(identity).mapValues(_.length)