這個問題在這里已經有了答案： 為什么這個涉及 list.index() 呼叫的 lambda 這么慢？ (1 個回答) 3 分鐘前關閉。
如果我有點新手，請原諒我，幾周前我開始自學如何編碼。
我一直在解決 cses.fi 上的一個問題。我遇到了“收集數字”問題，它本質上是在問我們：給定一個陣列，例如 [4, 2, 1, 5, 3]，我們必須“收集”多少次數字才能使這些數字井井有條按從 1 到 n 的遞增順序。
在這種特殊情況下，我們需要 3 輪，因為我們迭代一次并收集“1”，第二次迭代給我們“2, 3”，最后第三次將給我們“4, 5”。
我正在用 Python 編程并最終遇到了解決方案，盡管我在提交它時遇到了 TLE 錯誤。我做了一些調整，發現 .method() 大大減慢了我的代碼。
TLE 代碼：
n = int(input())
arr = list(map(int, input().split()))
i_arr = [0] * (n 1)
res = 1
for i in arr:
i_arr[i] = arr.index(i)
for i in range(1, len(i_arr)):
if i_arr[i] < i_arr[i - 1]:
res = 1
print(res)
運行時間為 0.09 秒的已接受代碼：
n = int(input())
arr = list(map(int, input().split()))
i_arr = [0] * (n 1)
for i in range(n):
i_arr[arr[i]] = i
res = 1
for i in range(1, len(i_arr)):
if i_arr[i] < i_arr[i - 1]:
res = 1
print(res)
這兩個代碼塊之間的唯一區別在于我在第一個 for 回圈中的索引方式。
我的問題是：python 中的 ,??index 方法慢嗎？如果是，為什么？謝謝你的幫助。
uj5u.com熱心網友回復：
是的，它會慢得多，尤其是隨著“n”的大小增長。
在 TLE 代碼中，您所說的是：
- 通過在陣列中搜索“i”來找到“i”的索引。請記住，python 程式不能假定串列是有序的或任何東西，因此它必須手動搜索第一次出現的 'i'
- 當 'n' 很小時，這很好，因為例如在第一次迭代期間，.index() 將首先查找 i=0 并快速回傳，因為串列中的第一個數字恰好是 0。
- 但想想隨著 n 的增長，你基本上是在要求 .index() 遍歷串列 1 更多點
- 這個 for 回圈就是所謂的 O(n^2) 演算法，因為對于“n”中的每個“i”，最壞的情況是搜索 n 個專案以找到要回傳的索引。更糟糕的情況發生在 for 回圈的最后一次迭代中。
您的第二個實作不需要像您的第一個實作那樣遍歷串列 n 次。
當然，就像我提到的，第一個實作不必每次都遍歷整個串列，但隨著回圈的繼續和“i”的增長，情況會變得更糟。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/441332.html