python - 无法理解解决方案背后的逻辑[FrogRiverOne]

Question

我无法理解 Codility FrogRiverOne 解决方案背后的逻辑是什么 https://codility.com/demo/take-sample-test/frog_river_one

任务描述

一只小 Frog 想要到达河的对岸。 Frog 最初位于河的一岸(位置 0)，想要到达对岸(位置 X+1)。叶子从树上落到河面上。

给你一个数组 A，它由 N 个表示落叶的整数组成。 A[K]表示一片叶子在时间K落下的位置，以秒为单位。

目标是找出 Frog 最早能跳到河对岸的时间。只有当从1到X过河的每个位置都出现树叶时， Frog 才能过河(即我们要找到从1到X的所有位置都被树叶覆盖的最早时刻)。您可能会假设河流中的水流速度小得可以忽略不计，即树叶落入河流后不会改变位置。

例如，给定整数 X = 5 和数组 A，这样:

  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4

第6秒，一片叶子落在第5个位置，这是河对岸各个位置最早出现叶子的时间。

写一个函数:

定义解决方案(X，A)

给定一个由 N 个整数和整数 X 组成的非空数组 A，返回 Frog 能跳到河对岸的最早时间。

如果 Frog 永远无法跳到河的另一边，函数应该返回-1。

例如，给定 X=5 和数组 A 使得:

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4

函数应该返回 6，如上所述。

假设:

N 和 X 是 [1 . 100,000]数组 A 的每个元素都是范围 (1 . X) 内的整数。复杂性:

预期的最坏情况时间复杂度为 O(N)；预期的最坏情况空间复杂度为 O(X)(不计算输入参数所需的存储空间)。

---

解决方案--

Input arguments to Function - (2,[2,2,2,2,2]) and (5, [1, 3, 1, 4, 2, 3, 5, 4])

def solution(X,A):

    covered = 0
    covered_a = [-1]*X

    for index,element in enumerate(A):
        if covered_a[element-1] == -1:

            covered_a[element-1] = element
            covered += 1
            if covered == X:
                return index
    return -1

我想了解创建 bool 数组并从输入数组 A 中减去 1 个元素背后的逻辑是什么

Answer 1

这是因为您想“标记”您目前看到的所有数字。所以它从所有这些都以“False”开始，因为您还没有看到它们中的任何一个。