找到两个数组相交的索引

Question

我想知道在 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 的复杂性不必要地大，因为两个数组总是会提前排序，所以单遍选项会更可取。

Answer 1

如果两个列表都存储，则看起来相当简单，只是 merge-sort.

的“合并”阶段的细微变化

@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 -> _) }

找到两个数组相交的索引

Find the indices at which two arrays intersect

scala