3 回答

TA貢獻1789條經驗 獲得超8個贊
您可以遍歷列表,將項目添加到集合中,如果該項目已經在集合中,則它是具有最低索引的重復項,因此您可以簡單地返回該項目; 或者如果您到達循環末尾而沒有找到重復項,則返回 -1:
def firstDuplicate(a):
seen = set()
for i in a:
if i in seen:
return i
seen.add(i)
return -1

TA貢獻1851條經驗 獲得超4個贊
創建一個新集合并在新列表中找到它,如果它返回元素:
def firstDuplicate(a):
dup = set()
for i in range(len(a)):
if a[i] in dup:
return a[i]
else:
dup.add(a[i])
return -1

TA貢獻1993條經驗 獲得超6個贊
這只是一個想法,我沒有驗證它,但它應該可以工作。似乎沒有內存限制,只有時間限制。因此,使用空間來交易時間可能是一種實用的方法。計算復雜度為O(n)。該算法還取決于數字范圍在 1 到 之間的條件len(a)。
def first_duplicate(a):
len_a = len(a)
b = [len_a + 1] * len_a
for i, n in enumerate(a):
n0 = n - 1
if b[n0] == len_a + 1:
b[n0] = len_a
elif b[n0] == len_a:
b[n0] = i
min_i = len_a
min_n = -1
for n0, i in enumerate(b):
if i < min_i:
min_i = i
min_n = n0 + 1
return min_n
更新:
此解決set()方案不如@blhsing的解決方案快。但是,如果它是用 C 實現的,可能就不一樣了——這有點不公平,因為它set()是一個內置函數,它是用 C 實現的,作為 CPython 的其他核心函數。
添加回答
舉報