Warm tip: This article is reproduced from serverfault.com, please click

scala-查找应该在其中插入元素以保持顺序的最后一个索引

(scala - Find last index where an element should be inserted in order to maintain order)

发布于 2020-11-27 23:43:16

我正在尝试在Scala中实现searchsorted算法(side = right),即找到应该在其中插入元素以维持排序顺序的最后一个索引。

对于前。

val arr = List(1,2,2,3,4,4,6,6). // assume list is sorted, also array can have negetive elements(albeit sorted)
if elem = 2, output index = 3
if elem = 3, output index = 4
if elem = 5, output index = 6
if elem = -3, output index = 0

我想到了这一点,遍历列表中的每个元素,并检查最小的差异

val a = List(1,1,2,2,3,3,4,5,5)
val elem = 1
val (_, index) = a
.foldLeft(Int.MaxValue, 0) {
    case ((smallestDiff, index), currNum) =>
        val currDiff = (elem - currNum).abs
        if (currDiff > smallestDiff) (smallestDiff, index)
        else (currDiff, index + 1)
}

这对于1st 2个示例正常工作,但对于最后2个ex则完全中断

Questioner
Neel_sama
Viewed
11
jwvh 2020-11-28 09:05:32

indexWhere() 可以完成大部分繁重的工作。

def insertHere(ns:Seq[Int], elem:Int):Int = {
  val idx = ns.indexWhere(_ > elem)
  if (idx < 0) ns.length
  else idx
}
insertHere(  List(1,2,2,3,4,4,6,6), 2) // 3
insertHere(   Seq(1,2,2,3,4,4,6,6), 3) // 4
insertHere( Array(1,2,2,3,4,4,6,6), 5) // 6
insertHere(Vector(1,2,2,3,4,4,6,6),-3) // 0
insertHere(  List(1,2,2,3,4,4,6,6),12) // 8

elem应在末尾附加时,这将返回不存在的索引