algorithm - Python Codility Frog River 一次复杂度

Question

所以这是另一个可能著名的 codility 平台的方法，关于 Frog 过河的任务。很抱歉，如果以不当的方式提出这个问题，这是我在这里的第一篇文章。

The goal is to find the earliest time when the frog can jump to the other side of the river. For example, given X = 5 and array A such that:

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

the function should return 6.

示例测试:(5, [1, 3, 1, 4, 2, 3, 5, 4])

完整任务内容: https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

所以这是我第一个明显的方法:

def solution(X, A):
    lista = list(range(1, X + 1))
    if X < 1 or len(A) < 1:
        return -1
    found = -1
    for element in lista:
        if element in A:
            if A.index(element) > found:
                found = A.index(element)
        else: return -1
    return found

X = 5
A = [1,2,4,5,3]
solution(X,A)

此解决方案 100% 正确，在性能测试中获得 0%。

所以我认为更少的行+列表理解会得到更好的分数:

def solution(X, A):
    if X < 1 or len(A) < 1:
        return -1
    try:
        found = max([ A.index(element) for element in range(1, X + 1) ])
    except ValueError:
        return -1
    return  found

X = 5
A = [1,2,4,5,3]
solution(X,A)

这个也可以工作，性能为 0%，但无论如何它更快。

我还找到了 deanalvero ( https://github.com/deanalvero/codility/blob/master/python/lesson02/FrogRiverOne.py ) 的解决方案:

def solution(X, A):
    # write your code in Python 2.6
    frog, leaves = 0, [False] * (X)
    for minute, leaf in enumerate(A):
        if leaf <= X:
            leaves[leaf - 1] = True
        while leaves[frog]:
            frog += 1
            if frog == X: return minute
    return -1

此解决方案在正确性和性能测试中获得 100% 的成绩。

我的问题出现可能是因为我不太了解这个时间复杂度的事情。请告诉我最后一个解决方案比第二个解决方案更好吗？它在 for 循环中有一个 while 循环!它应该很慢，但事实并非如此。

Answer 1

这是一个解决方案，您可以在其中获得 100% 的正确性和性能。

def solution(X, A):
    i = 0
    dict_temp = {}
    while i < len(A):
        dict_temp[A[i]] = i
        if len(dict_temp) == X:
            return i
        i += 1
    return -1