使用python排队系统的问题

Question

我有一系列的名字：队列安德鲁，队列亚历克斯，队列艾米，亚历克斯约翰，亚历克斯彼得，约翰杰米，杰米杰克，约翰亚当

我尝试创建的函数将这些名称排队。名字中有Queue的名字将被正常添加，前面有其他人名字的名字将在队列中这些名字后面排队。所以上面给出的数组的答案是安德鲁，亚历克斯，约翰，杰米，杰克，亚当，彼得，艾米

这是我用来做这件事的函数：

def test(arr):
    timer =0
    usedname ="pop"
    newlist=[]
    for i in arr:
        new_string = i.replace("MainQueue ","")
        newlist.append(new_string)
    ans=newlist
    for i in range(len(newlist)):
        if (len(newlist[i].split()) > 1):
            x = newlist[i].split() 
            y = ans.index(x[0])  
            name=x[1]  
            if x[0] == usedname:
                timer+=1
                newlist.remove(newlist[i])
                ans.insert(y+timer,name)
            else:
                timer =1
                newlist.remove(newlist[i])
                ans.insert(y+timer,name)
                usedname = x[0];
    print(' '.join(ans))

但我得到的结果是安德鲁·亚历克斯·约翰·亚当·杰米·杰克·彼得·艾米

我不知道我需要做什么改变才能继续这样做，我觉得我尝试的解决方案可能太复杂了

Answer 1

我发现此功能满足您的要求：

input_array = ["Queue Andrew", "Queue Alex", "Queue Amy", "Alex John", "Alex Peter", "John Jamie", "Jamie Jack", "John Adam"]

def test(arr):
    result = []
    for elem in arr[:]:
        a, b = elem.split()
        if a == "Queue":
            result.append(b)
            arr.remove(elem)
    i = len(arr) #starts at the end of the list (for iterating in reverse)
    while 0 < len(arr): # only as long as there are names left
        i -= 1 # next element (normally i += 1 but reversed)
        if i < 0: # if loop reached the front of the list, start over from the end.
            i = len(arr)-1 #start again from the end
        a, b = arr[i].split()
        if a in result:
            result.insert(result.index(a) + 1, b)
            arr.remove(arr[i])
    return result

print(test(input_array))

#prints ['Andrew', 'Alex', 'John', 'Jamie', 'Jack', 'Adam', 'Peter', 'Amy']

首先，它将所有“队列名称”元素添加到列表中。 然后，它迭代其余的条目，直到arr为空（按相反顺序，以便结果正确），并在另一个名称（result.index(a)+1）的索引后面插入名称（result.insert()）

如果我没有弄错的话，这个算法有最坏的O(n^2)和最好的O(n)

编辑

以相反的顺序迭代列表会使它更复杂一些。我们需要从i=len(arr)开始，而不是从i=0开始。然后对于每个迭代，我们将i减少1。 循环在数组上迭代多次，直到它为空。因此，如果i到达第0个元素，它需要从arr的末尾重新开始