a=[2, 1, 3, 5, 3, 2]def firstDuplicate(a): for i in range(0,len(a)): for j in range(i+1,len(a)): while a[i]==a[j]: num=[j] break print(num)print(firstDuplicate(a))輸出應該是4和5，但是只有4
2 回答
蝴蝶不菲
TA貢獻1810條經驗 獲得超4個贊
您可以在O（n）時間和O（1）多余空間中找到數組中所有重復項的索引，如下所示：
def get_duplicate_indices(arr):
inds = []
for i, val in enumerate(arr):
val = abs(val)
if arr[val] >= 0:
arr[val] = -arr[val]
else:
inds.append(i)
return inds
get_duplicate_indices(a)
[4, 5]
注意，這將修改數組！如果要保持輸入數組不變，則將上面的前幾行替換為：
def get_duplicate_indices(a):
arr = a.copy() # so we don't modify in place. Drawback is it's not O(n) extra space
inds = []
for i, val in enumerate(a):
# ...
從本質上講，這使用數組中每個元素的符號作為以前是否看到過數字的指示器。如果我們遇到一個負值，則意味著我們已經看過達到的數字，因此我們將數字的索引附加到我們已經看到的索引列表中。
請注意，如果數組中的值大于數組的長度，則可能會遇到麻煩，但是在這種情況下，我們只是將工作數組擴展為與輸入中的最大值相同的長度。十分簡單。
GCT1015
TA貢獻1827條經驗 獲得超4個贊
您的代碼有些錯誤。以下將收集每個第一個重復項的索引：
def firstDuplicate(a):
num = [] # list to collect indexes of first dupes
for i in range(len(a)-1): # second to last is enough here
for j in range(i+1, len(a)):
if a[i]==a[j]: # while-loop made little sense
num.append(j) # grow list and do not override it
break # stop inner loop after first duplicate
print(num)
當然，還有更多性能算法可以實現這一點，而不是二次方的。
添加回答
舉報
0/150
提交
取消