如何找到重複的第一個實例的兩個相等長度的位置，排序的列表

Question

我有兩個相同長度的隨機清單，在0至99之間

lista = [12,34,45,56,66,80,89,90] 

listb = [13,30,56,59,72,77,80,85] 

我需要找到的第一個實例一個重複號碼，以及它來自哪個列表。 在這個例子中，我需要在listb中找到數字'56'，並獲得索引i = 2

謝謝。

更新： 運行它了幾次後，我得到這個錯誤：

if list_a[i] == list_b[j]: 
IndexError: list index out of range 

像@Asterisk建議，我的兩個列表是相等的長度和排序，i和j是在設置爲0開始。 所述位是一個遺傳交叉代碼部分：

def crossover(r1,r2): 
    i=random.randint(1,len(domain)-1) # Indices not at edges of domain 
    if set(r1) & set(r2) == set([]): # If lists are different, splice at random 
     return r1[0:i]+r2[i:] 
    else: # Lists have duplicates 
     # Duplicates At Edges 
     if r1[0] == r2[0]: # If [0] is double, retain r1 
     return r1[:1]+r2[1:] 
     if r1[-1] == r2[-1]: # If [-1] is double, retain r2 
     return r1[:-1]+r2[-1:] 
     # Duplicates In Middle 
     else: # Splice at first duplicate point 
     i1, i2 = 0, 0 
     index =() 
     while i1 < len(r1): 
      if r1[i1] == r2[i2]: 
      if i1 < i2: 
       index = (i1, r1, r2) 
      else: 
       index = (i2, r2, r1) 
      break 
      elif r1[i1] < r2[i2]: 
      i1 += 1 
      else: 
      i2 += 1 
     # Return A Splice In Relation To What List It Appeared First 
     # Eliminates Further Duplicates In Original Lists 
     return index[2][:index[0]+1]+index[1][index[0]+1:] 

該函數採用2所列出並返回一個。 域是一個10個簇的列表：（0,99）。

正如我所說，錯誤不會發生在每一次，只有一段時間。

我感謝您的幫助。

Answer 1

lista = [12,34,45,56,66,80,89,90] 

listb = [13,30,56,59,72,77,80,85] 

i, j = 0, 0 
while i < len(lista):  
    if lista[i] == listb[j]: 
     if i < j: 
      print i, lista 
     else: 
      print j, listb 
     break 
    elif lista[i] < listb[j]: 
     i += 1 
    else: 
     j += 1 


>>> 
2 [13, 30, 56, 59, 72, 77, 80, 85] 

假設：兩個列表具有相同的長度，並且它們被排序

Answer 2

我不是一個Python的傢伙，但是這是一個算法的問題...

您維護索引到每一個列表，你看在這兩個列表中的位置的元素。

無論哪個列表在當前位置有最小的元素，您將移動到該列表中的下一個元素。

當您找到與另一個列表的當前元素相同的元素時，這是您的最小副本。

如果到達任一列表的末尾，則沒有重複項。

Answer 3

如果你正在尋找所有的副本，你可以使用這樣的事情：

list_a = [12,34,45,56,66,80,89,90] 
list_b = [13,30,56,59,72,77,80,85] 

set_a = set(list_a) 
set_b = set(list_b) 

duplicates = set_a.intersection(set_b) 
# or just this: 
# duplicates = [n for n in list_a if n in list_b] 

for duplicate in duplicates: 
    print list_a.index(duplicate) 

要獲得一個重複的最小指數在任一列表：

a_min = min(map(list_a.index, duplicates)) 
b_min = min(map(list_b.index, duplicates)) 

if a_min < b_min: 
    print 'a', a_min, list_a[a_min] 
else: 
    print 'b', b_min, list_b[b_min] 

如果不是，這應該會好一點：

duplicate = None 

for n in set_a: 
    if n in set_b: 
     duplicate = n 
     break 

if duplicate is not None: 
    print list_a.index(duplicate) 

Answer 4

只需掃描位置0處的所有列表，然後是1，然後是2，...跟蹤您所看到的內容（您可以查詢設置在O（1）時間）。

def firstDuplicate(*lists): 
    seen = {} 
    for i,tup in enumerate(zip(*lists)): 
     for listNum,value in enumerate(tup): 
      position = (listNum,i) 
      if value in seen: 
       return value, [seen[value], position] 
      else: 
       seen[value] = position 

演示：

>>> value,positions = firstDuplicate(lista,listb) 
>>> value 
56 
>>> positions 
[(1, 2), (0, 3)] 

（不推廣到N列表...但。需要稍作調整，使用defaultdict(set)，將所有索引作爲元組插入在一起，然後檢查重複項。）