arrays - 我为这个hackerrank测试编写的代码可以工作，但是资源太多，现在我没有想法了。我究竟做错了什么？

Question

新年混沌问题：Hackerrank

这是我编写的程序，它告诉我我的代码没有及时完成（并且我需要优化它以使其在更短的时间内完成）。我已经尽我所能，但我没有想法，我该怎么办？

fun minimumBribes(q: Array<Int>) {
    var bribeCount = 0
    for ((i, x) in q.withIndex()) {

        val last = q.lastIndex - i + 1
        val first = i + 1


        // Checks if any of the elements have more than 2 elements smaller than them behind them in the queue and returns out of the function if so (because no element can bribe more than 2 elements)
        // Drops all the elements in the queue before x and counts the number of smaller elements after x in the queue
        if (q.drop(first).count { it < x } > 2) {
            println("Too chaotic")
            return
        }

        // Adds the number of elements bigger than x that are in the queue standing ahead of x to bribeCount (since the number of bribes taken by all elements will be equal to the total number of bribes given in total and no element can get past ahead of a smaller element without bribing it)
        bribeCount += q.dropLast(last).count { it > x }

    }
    println(bribeCount)
}

阅读页面顶部链接的第一个问题。在阅读问题陈述之前，您可能不会理解此行以下的任何内容。

如您所见，为了检查贿赂元素的人数，我计算了从该元素中具有更大价值并且在队列中站在它之前的元素的数量。通过将每个元素收到的贿赂数量相加，我们可以计算出总共提供的贿赂数量。但在此之前，我计算了小于队列中位于其后面的元素的元素数量，如果该数量大于 2，则表示该元素贿赂了超过 2 个人，这是“太混乱”，我返回。

这是我收到的错误消息：截图

标签： arraysperformanceloopskotlin

Answer 1

您的代码的问题在于它使用了太多循环。

1. 两者都Array.drop(Int)使用Array.dropLast(Int)循环来构造 a List，然后返回。
2. Iterable<T>.count((T) -> Boolean)使用循环来计算指定条件为真的次数。

要优化您的代码，请删除这些使用循环的扩展函数。

fun minimumBribes(queue: Array<Int>): Unit {
    var bribeCount = 0

    for ((index, initialPosition) in queue.withIndex()) {
        val currentPosition = index + 1

        if ((initialPosition - currentPosition) > 2) {
            println("Too chaotic")
            return
        }

        val startingCheckIndex = max(0, initialPosition - 2)

        for (checkIndex in startingCheckIndex until index) {
            val hasBribed = queue[checkIndex] > initialPosition
            if (hasBribed) bribeCount++
        }
    }

    println(bribeCount)
}

澄清：

对于队列中的每个号码：

1： 我们检查一个人在队列中向上移动了多远，即initialPosition - currentPosition。如果他/她已经上升了 2 个以上的位置，那么我们打印“太混乱”并返回控制权，因为这个人不可能在他/她之前贿赂超过 2 个人。

例如，如果这个人的贴纸上写着 6，而他的当前位置是 3，那么这个人已经向上移动了 3 个位置，这是不可能的。

2：你在问题中提到，I count the number of elements that have a bigger value from that element and are standing before it in the queue。

这是正确的，因为我们正在计算一个人收受了多少贿赂，但我们无法直接检查到第一个位置。由于贿赂他人的人只能在他之前移动一个位置，因此我们只会在该人的初始位置之前检查最多 1 个位置。startingCheckIndex我在我的代码中调用了这个位置的索引。

例如：如果该人的贴纸上写着 5，而当前位置是 10。那么我们将仅从位置 4 到 10 进行检查。

请注意，我使用过max(0, initialPosition - 2).
-2因为数组索引从0开始，initialPosition从1开始。
max(0,..)因为对于initialPosition 1，1 - 2 = -1所以我们需要保持最小值为0。