2

我有两个相同长度的随机列表，范围为 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 个列表并返回一个。domain 是 10 个元组的列表：(0,99)。

正如我所说，错误不会每次都发生，只会偶尔发生一次。

我感谢您的帮助。

4

4 回答 4

1

我不是 python 人，但这是一个算法问题......

您维护每个列表的索引，并查看这两个列表位置的元素。

无论哪个列表在当前位置具有最小元素，您都将移动到该列表中的下一个元素。

当您找到一个与另一个列表的当前元素相同的元素时，这就是您的最小副本。

如果您到达任一列表的末尾，则没有重复项。

于 2012-10-05T02:48:01.363 回答
1

如果您要查找所有重复项，则可以使用以下内容：

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)
于 2012-10-05T02:48:08.230 回答
0

只需扫描位置 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 个列表...。需要稍作调整才能使用 a defaultdict(set)，将所有索引作为元组插入在一起，然后检查重复项。）

于 2012-10-05T03:21:54.287 回答
0 
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]

假设：两个列表具有相同的长度，并且它们已排序

于 2012-10-05T03:14:14.403 回答