python - 在几乎无限的列表中查找元素

Question

我正在尝试解决这个问题:

A list is initialized to ["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"], and then undergoes a series of operations. In each operation, the first element of the list is moved to the end of the list and duplicated. For example, in the first operation, the list becomes ["Leonard", "Penny", "Rajesh", "Howard", "Sheldon", "Sheldon"] (with "Sheldon" being moved and duplicated); in the second operation, it becomes ["Penny", "Rajesh", "Howard", "Sheldon", "Sheldon", "Leonard", "Leonard"] (with "Leonard" being moved and duplicated); etc. Given a positive integer n, find the string that is moved and duplicated in the nth operation. [paraphrased from https://codeforces.com/problemset/problem/82/A]

我已经写了一个可行的解决方案，但是当 n 很大时它太慢了:

l = ['Sheldon','Leonard','Penny','Rajesh','Howard']
n = int(input()) # taking input from user to print the name of the person
                 # standing at that position

 for i in range(n):
    t = l.pop(0)
    l.append(t)
    l.append(t)

    #debug
    # print(l)

print(t)

我怎样才能更快地做到这一点？

Answer 1

这是一个在 O(log(input/len(l))) 中运行但不进行任何实际计算(无列表操作)的解决方案:

l = ['Sheldon','Leonard','Penny','Rajesh','Howard']
n = int(input()) # taking input from user to print the name of the person
                 # standing at that position

i = 0
while n>(len(l)*2**i):
    n = n - len(l)* (2**i)
    i = i + 1

index = int((n-1)/(2**i ))

print(l[index])

说明:每次将整个列表推回时，列表长度将恰好增长 len(l) x 2^i。但是你必须首先找出这种情况发生了多少次。这就是 while 正在做的事情(这就是 n = n - len(l)* (2**i) 正在做的事情)。当 while 意识到将发生 i 次追加双列表时，while 停止。最后，在计算出 i 之后，您必须计算索引。但是在第 i 个附加列表中，每个元素都被复制 2^i 次，所以你必须将数字除以 2**i。一个小细节是，对于索引，您必须减去 1，因为 Python 中的列表是 0 索引的，而您的输入是 1 索引的。