Python Codility Frog River 一次复杂度

问题描述 投票：0回答：13

因此，这是可能著名的 codility 平台的另一种方法，即青蛙过河任务。很抱歉，如果这个问题是以不好的方式提出的，这是我在这里的第一篇文章。

目标是找到青蛙最早能跳到河对岸的时间。 例如，给定 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, [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/dealvero/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循环！应该很慢，但事实并非如此。

algorithm performance time-complexity
13个回答
3
投票

使用 set()

具有出色的性能 

def solution(X, A): 
     
    positions = set() 
    seconds = 0 
 
    for i in range(0, len(A)): 
        if A[i] not in positions: 
            positions.add(A[i]) 
            seconds = i 
     
    if len(positions) == X: 
        return seconds

    return -1

或者使用 dictionary

具有出色性能的另一种解决方案 
def solution(X, A):
    positions = {}
    count = 0
    seconds = -1

    for i in range(len(A)):
        if A[i] not in positions:
            positions[A[i]] = i
            count += 1
            if count == X:
                seconds = i
                break

    return seconds
2
投票

这是一个解决方案，您可以在其中获得 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
2
投票

答案已经告诉过，但我将添加一个可选的解决方案，我认为可能会帮助您理解：

def save_frog(x, arr):
    # creating the steps the frog should make
    steps = set([i for i in range(1, x + 1)])

    # creating the steps the frog already did
    froggy_steps = set()

    for index, leaf in enumerate(arr):
        froggy_steps.add(leaf)
        if froggy_steps == steps:
            return index
    return -1
0
投票

嵌套循环的数量并不能直接告诉你任何关于时间复杂度的信息。令 n 为输入数组的长度。 while 循环内部需要 average O(1) 时间，尽管其最坏情况时间复杂度为 O(n)。快速解决方案使用布尔数组leaves，其中如果存在叶子，则每个索引的值都为true，否则为false。整个算法中 while 循环内部的执行次数不超过 n 次。外部 for 循环也仅执行 n 次。这意味着该算法的时间复杂度为O(n)。

0
投票

关键是你的两个初始解都是二次的。它们涉及对父元素的each进行 O(n) 内部扫描（导致 O(n**2)）。

快速解决方案最初似乎遭受了同样的命运，因为很明显它包含一个循环中的一个循环。但是内部 while 循环并没有完全扫描每个“叶子”。看一下“frog”的初始化位置，您会注意到 while 循环有效地从每片叶子停止的位置开始。

0
投票

def solution(X, A): covered = [False] * (X+1) n = len(A) Sx = ((1+X)*X)/2 # sum of the numeric progression for i in range(n): if(not covered[A[i]]): Sx -= A[i] covered[A[i]] = True if (Sx==0): return i return -1 




      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        
set
，这不是很好。
def solution(X, A):
    found = set()
    for pos, i in enumerate(A, 0):
        if i <= X:
            found.add(i)
            if len(found) == X:
                return pos
    return -1



还有一种针对二进制数组的优化解决方案


def solution(X, A):
    steps, leaves = X, [False] * X
    for minute, leaf in enumerate(A, 0):
        if not leaves[leaf - 1]:
            leaves[leaf - 1] = True
            steps -= 1
            if 0 == steps:
                return minute
    return -1



最后一种更好，资源更少。与二进制列表相比，集合消耗更多资源（内存和CPU）。

    





      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        

    



      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        


def solution(X, A):
    if (X > len(A)): # check for no answer simple
        return -1
    elif(X == 1):    # check for single element
        return 0
    else:
        std_set = {i for i in range(1,X+1)} # list of standard order
        this_set = set(A)                   # set of unique element in list
        if(sum(std_set) > sum(this_set)):   # check for no answer complex
            return -1
        else:
            for i in range(0, len(A) - 1):  
                if  std_set:
                    if(A[i] in std_set):
                        std_set.remove(A[i]) # remove each element in standard set
                if not std_set:              # if all removed, return last filled position
                    return(i)



我想这段代码可能无法满足运行时的要求，但它是我能想到的最简单的

    





      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        


def solution(X, A):
    from collections import OrderedDict as od
    if sum(set(A))!=(X*(X+1))//2:
        return -1
    k=list(od.fromkeys(A).keys())[-1]
    for x,y in enumerate(A):
        if y==k:
            return x


    



      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        


def solution(x, a):
    # write your code in Python 3.6
    # initialize all positions to zero
    # i.e. if x = 2; x + 1 = 3
    # x_positions = [0,1,2]
    x_positions = [0] * (x + 1)

    min_time = -1
    for k in range(len(a)):
        # since we are looking for min time, ensure that you only
        # count the positions that matter
        if a[k] <= x and x_positions[a[k]] == 0:
            x_positions[a[k]] += 1
            min_time = k

    # ensure that all positions are available for the frog to jump
    if sum(x_positions) == x:
        return min_time
     return -1


    



      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        


def solution(X, A): 
     
    positions = set()
 
    for i in range(len(A)): 
        if A[i] not in positions: 
            positions.add(A[i]) 
     
        if len(positions) == X: 
            return i

    return -1


    



      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        


def solution(X, A):
    s = set()
    for i, leaf in enumerate(A):
        s.add(leaf)
        if len(s) == X: 
            return i 
    return -1


    

      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.