令人驚訝的蟒蛇組合方法訂單

Question

我知道，set() python沒有訂單，因爲它是作爲一個哈希表實現的。然而，我有點驚訝地解決了一個涉及使用set.intersection()的命令的問題。

因此，我給出了兩個列表的順序，例如說，表示一些排名或發生順序。我必須找到兩個列表中共同的元素，並且在兩個列表中具有最高的順序（發生在第一個）。例如，

List1 = ['j','s','l','p','t'] 
List2 = ['b','d','q','s','y','j'] 

應該輸出's'因爲它是在List1第二好的並且發生在List2第一個。

如果您將每個列表轉換爲集合並採用路口Set1.intersection(Set2)，則會得到一組set(['s', 'j'])。在我的情況下，我可以將其轉換爲列表並吐出第一個元素，這大約是O（n1 + n2）。

我很高興解決這個面試問題（所有測試都通過了），但我很驚訝，我怎麼能用python set來解決這樣的訂單基礎問題。

有沒有人有線索如何工作？什麼是可能的情況，這可能會崩潰？

編輯：這似乎是一樣的運氣盒的行程，所以如果你有這個問題的很好的解決方案，這將是還讚賞

Answer 1

列表解析可以做的工作：

Set2 = set(List2) 
[x for x in List1 if x in Set2] 

這將保持List1的順序，您也可以對List2執行相同的操作。

然後，您可以在清單理解（或生成器更高效）上撥打next以獲得第一個匹配。

Answer 2

我找到了一個O(n1+n2)的方法。評論代碼如下。訣竅是創建一個查找表（而不是一個字典，一個簡單的數組）來索引兩個列表中的字母的最小位置，然後找到這些位置和相關字母之和的最小值。

List1 = ['j','s','l','p','t'] 
List2 = ['b','d','q','s','y','j'] 

# unreachable max value to initialize the slots 
maxlen = max(len(List1),len(List2))+1000 

# create empty slot_array (initialized to values higher than last letter pos 
# for both lists (the value is greater than any "valid" position) 
# first pos (index 0) is for letter "a", last pos is for letter "z" 

slot_array = [[maxlen,maxlen] for x in range(ord('a'),ord('z')+1)] 

# scan both lists, and update the position if lower than the one in slot_array 
for list_index,the_list in enumerate((List1,List2)): 
    print(list_index) 
    for letter_index,letter in enumerate(the_list): 
     slot = slot_array[ord(letter)-ord('a')] 
     if slot[list_index]>letter_index: 
      slot[list_index] = letter_index 

# now compute minimum of sum of both minimum positions for each letter 
min_value = maxlen*2 

for i,(a,b) in enumerate(slot_array): 
    sab = a+b 
    if sab < min_value: 
     min_value = sab 
     min_index = i 

# result is the letter with the minimal sum 
print(chr(min_index+ord('a')))