如何在Scala中高效统计特定整数在数组中的出现频次

你当前的嵌套循环实现时间复杂度为O(len(A)*len(B))，数组规模较大时性能损耗明显。优化核心思路是仅遍历B数组1次统计所有元素的出现次数，再按A的顺序提取对应频次，整体时间复杂度可以降到O(len(A)+len(B))，性能提升非常显著。

方案1：基础语法实现（仅用到你已掌握的for、if逻辑，学习成本低） #

你可以借助可变映射存储元素的出现频次，逻辑如下：

import scala.collection.mutable.HashMap

// 第一步：遍历B一次统计所有元素的出现次数
val countMap = HashMap[Int, Int]()
for (num <- B) {
  if (countMap.contains(num)) {
    countMap(num) += 1
  } else {
    countMap(num) = 1
  }
}

// 第二步：按A的顺序生成结果数组C，仅遍历A一次
val C = new Array[Int](A.length)
var idx = 0
for (num <- A) {
  C(idx) = countMap(num) // 因为B的元素全部来自A，不需要处理不存在的情况
  idx += 1
}

// 输出结果
for (cnt <- C) {
  println(cnt)
}

方案2：Scala原生简洁写法（利用内置API减少样板代码） #

后续你熟悉Scala集合API后，可以用更短的代码实现完全相同的逻辑，性能和方案1一致：

// 统计B的元素频次
val countMap = B.groupBy(identity).view.mapValues(_.length).toMap
// 按A的顺序生成结果数组
val C = A.map(countMap(_))

// 输出
C.foreach(println)

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