一跳飛行挑戰

我有一個從源到目的地的航班元組列表。例如：[（2,3），（1,2），（3,1），（1,3），（3,2），（2,4），（4,1）]一跳飛行挑戰

想返回所有航班之間有一個連接航班的元組列表。例如，上面列表的答案是[（1,2），（1,3），（1,4），（2,1），（3,2），（3,4），（4 ，2），（4，3）]

我是python的初學者，一直試圖解決它很長一段時間，現在想出了下面的代碼。我的邏輯錯了嗎？我覺得我可以使用列表解析或其他方法，但我不太確定。請給我一些關於如何去做這件事的建議。

def one_hop(l): 
    source = [i[0] for i in l] 
    dest = [j[1] for j in l] 
    (i, j, one) = (0, 0, []) 
    for i in source: 
     for j in dest: 
      if source.index(i) != dest.index(j) and j in dest and i != j: 
       index1 = dest.index(j) 
       if source[index1] in dest and source[index1] != j and dest.index(source[index1]) != source.index(i) and i == source[dest.index(source[index1])]: 
        one.append((i,j)) 
    return one

來源

2017-08-22 Kylo Ren

，你要求的理解（雖然這是低效）：

sorted(set((u[0],v[1]) for u in l for v in l if u[1]==v[0] and u[0]!=v[1]))

來源

2017-08-22 16:34:30 stefan

這個工作，謝謝！爲什麼它會效率低下？ –

它具有二次複雜性i。即對於每一個元素它遍歷每個元素。考慮10000個機場，最大10000 * 9999 = 10e8個航班。假設有10^6個航班，結果是10^12個一站式檢查。我假設e有更高效的算法。 G。建立圖表。 – stefan

一跳飛行挑戰

回答

相關問題