我想知道在 Scala 中是否有一種不錯的方法來獲取兩個陣列相交的索引。
所以給定陣列：
a1 = [0, 5, 10, 15, 20, 25, 30]a2 = [10, 20, 30, 40, 50]
理想情況下，利用兩個陣列都是有序且不包含重復的事實。
這些共享共同的元素a1.intersect(a2) = [10, 20, and 30]。這些元素出現的索引（位置）對于每個陣列都是不同的。
我想生成一個元組序列，其中包含它們相交的每個串列中的位置：
intersectingIndices(a1, a2) = [(2, 0), (4, 1), (6, 2)]
雖然intersect給出了相交值，但我需要知道原始索引，并且不希望不必進行 O(N) 掃描來找到每個索引 - 因為這些陣列變得非常長（數百萬個元素）。我還懷疑 的復雜性intersect太大了，因為兩個陣列總是會提前排序，所以單通道選項會更好。
uj5u.com熱心網友回復：
如果兩個串列都被存盤，它看起來相當簡單，只是合并排序的“合并”階段的輕微變化。
@taiilrec
def intersect(
left: List[Int],
right: List[Int],
lidx: Int = 0,
ridx: Int = 0,
result: List[(Int, Int)] = Nil
): List[(Int, Int)] = (left, right) match {
case (Nil, _) | (_, Nil) => result.reverse
case (l::tail, r::_) if l < r => intersect(tail, right, lidx 1, ridx, result)
case (l::_, r::tail) if l > r => intersect(left, tail, lidx, ridx 1, result)
case (l::ltail, r::rtail) => intersect(ltail, rtail, lidx 1, ridx 1, (lidx, ridx) :: result)
}
或者只是散列一個串列，然后掃描另一個（它仍然是 O(n)，雖然有點貴，但更簡單）：
val hashed = left.zipWithIndex.toMap
right.zipWithIndex.flatMap { case(x, idx) => hashed.get(x).map(idx -> _) }
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/459003.html
標籤：斯卡拉