时间戳

首页 > 解决方案 > 分布在各个房间的用户索引

scala - 分布在各个房间的用户索引

问题描述

我是stackoverflow的新手，所以如果我不恰当地解释我的问题，请指导我。

我有一个长度为 N (an Array[Int]) 的整数集合，其中某个索引处的每个元素都i表示 room 中存在的用户数Ri。在 roomRi中，还对用户进行索引，使得第一个房间中的用户的索引是 from 1to R1，第二个房间包含R1 + 1 to R1 + R2等等。

现在输入是用户的索引，我需要找出用户在哪个房间。

我的解决方案是这样的：

def getRoomNumber(userIndex: Int, userDistribution: Array[Int]): Int = {

    val cummulativeRooms: Array[Int] = 
        rooms.tail.scanLeft(rooms.head)((x, y) => x + y)

    val roomIndex = cummulativeRooms.takeWhile(_ < userIndex).length + 1

    roomIndex
}

在这里，因为用户 4 将出现在房间 2 中（因为房间有这样的用户分布：Room1(U1, U2), Room2(U3, U4, U5)）。

我的代码对此输入工作正常。但是我有一些隐藏的测试用例，其中一半通过了。但后半部分没有，有些甚至抛出异常。

谁能告诉我我的代码有什么问题。你还有其他比这更有效的算法吗？

更多解释——

假设我有 10 个用户 - U1、U2、U3、U4、U5，我们按照userDistribution数组 - Array(2, 3) 定义的顺序将它们分成 N 个房间。这意味着用户 U1 和 U2 将出现在房间 1 中，而从 U3 到 U5 的用户将出现在房间 2 中。

现在，如果我想找出用户 U4 在哪里，那么输出应该是 2。输入是用户索引，在这种情况下是 4 和userDistribution数组 - Array(2, 3)

编辑：代码更改为函数。输入是我们要查找的用户索引，并userDistributions包含按顺序出现在每个房间中的用户数量。

编辑：约束是（我们不必在代码中检查这些约束） - N 和 Ui 的值都可以在 1 到 10e5 之间。此外，Ui 将小于数组的总和。

标签： scalaoptimizationsequence

解决方案

如果我正确理解了这个问题，您只需要迭代用户的分布数组并保留您看到的用户数量的总和，直到该总和大于或等于目标用户。

您可以使用命令式解决方案轻松做到这一点：

// Return Option because we can not guarantee the constraints.
// Also, ArraySeq is just an immutable array.
def imperativeSolution(userDistribution: ArraySeq[PositiveInt])(targetUser: PositiveInt): Option[PositiveInt] = {
  var acc = 0
  for (i <- userDistribution.indices) {
    acc += userDistribution(i)
    if (targetUser <= acc) return Some(i + 1)
  }
  None
}

然而，由于可变性和return.
我们可能宁愿使用递归方法：

// It is better to use a recursive data structure like List for a recursive algorithm.
def recursiveSolution(userDistribution: List[PositiveInt])(targetUser: PositiveInt): Option[PositiveInt] = {
  @annotation.tailrec
  def loop(remaining: List[PositiveInt], idx: PositiveInt, acc: PositiveInt): Option[PositiveInt] =
    remaining match {
      case x :: xs =>
        val newAcc = acc + x
        if (targetUser <= newAcc) Some(idx)
        else loop(remaining = xs, idx + 1, newAcc)
      
      case Nil =>
        None
    }
  
  loop(remaining = userDistribution, idx = 1, acc = 0)
}

这是不可变的，但它有很多样板，我们可以使用更实用的解决方案来减少这些样板并使其更具表现力：

def functionalSolution(userDistribution: IterableOnce[PositiveInt])(targetUser: PositiveInt): Option[PositiveInt] =
  userDistribution
    .iterator
    .scanLeft(0)(_ + _)
    .zipWithIndex
    .collectFirst {
      case (acc, idx) if (targetUser <= acc) => idx
    }

你可以看到他们在这里运行。

推荐阅读