在 Scala 中以线性时间检查数组内容是否相等
Checking Array content equality in linear time in Scala
我想检查 2 个整数数组(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
}
我遇到的问题:
- 默认地图是不可变的,我使用可变地图重建了剖面图。这将如何影响性能?
- 我遇到这个编译错误:
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。
不是通过算法修改,而是清除编译错误:
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)
forall
优于 fold
,因为当条件不匹配时可以在两者之间中断。 (尝试将打印语句放入匹配中以进行验证)
或者你可以这样做:
target.groupBy(identity).mapValues(_.length) == arr.groupBy(identity).mapValues(_.length)
我想检查 2 个整数数组(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
}
我遇到的问题:
- 默认地图是不可变的,我使用可变地图重建了剖面图。这将如何影响性能?
- 我遇到这个编译错误:
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。
不是通过算法修改,而是清除编译错误:
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)
forall
优于 fold
,因为当条件不匹配时可以在两者之间中断。 (尝试将打印语句放入匹配中以进行验证)
或者你可以这样做:
target.groupBy(identity).mapValues(_.length) == arr.groupBy(identity).mapValues(_.length)