我想將串列 a 的每個元素與其之前的連續元素進行比較。i 在前向的每次迭代需要對 j 在后向的迭代次數（或簡單地從 i 的當前索引反向迭代 j）并比較之前的連續元素是否滿足條件 a[i] >= a[j] . 如果條件為真，則將計數加 1 (count ) 如果條件失敗（即 a[i] < a[j] 在任何索引處）將計數附加到新串列 li[] 并列印 li。
我嘗試了以下方法但失敗了：
a = [1,2,3,2,4,6,1,2]
li=[]
count = 0
for i in range(len(a)):
for j in range(i,0,-1):
while a[i] >= a[j]:
count =1
li.append(count)
print(li)
輸出應如下所示：
1 2 3 1 5 6 1 2
有沒有什么具體的方法可以解決這個復雜度為 O(n) 的問題。就像有什么演算法可以解決在某種方法中需要 2 個或更多嵌套回圈的問題，以優化時間復雜度。
uj5u.com熱心網友回復：
使用 numpy 您可以評估整個np.array. 這為您節省了一個回圈。第一步創建包含數字大于當前值的所有索引的陣列：（array([1, 2, 3, 4, 5]對于原始串列的索引 6）。
在第二步中，空陣列被添加li為當前索引 1，idx 1因為這是該點必須回傳多遠（直到串列開始）。如果陣列非空，則將添加與idx最大值（即index-array 中最右邊的索引）之間的差值。同樣，這是指標必須移動的距離。
import numpy as np
a = np.array([1, 2, 3, 2, 4, 6, 1, 2])
li = []
for idx, val in enumerate(a):
index = np.where(a[0:idx 1] > val)
if np.size(index) == 0:
li.append(idx 1)
else:
li.append(idx - np.max(index))
print(li)
uj5u.com熱心網友回復：
這是來自需要堆疊在線性時間內解決的前瞻或后視問題類別：
def smaller_preceding(a):
stack = []
result = []
for i, x in enumerate(a):
while stack and a[stack[-1]] < x:
stack.pop()
# current index minus index of last bigger element!
result.append(i - (stack[-1] if stack else -1))
stack.append(i)
return result
>>> smaller_preceding([1,2,3,2,4,6,1,2])
[1, 2, 3, 1, 5, 6, 1, 2]
堆疊跟蹤嚴格減少元素的索引，例如，在某一時刻它將是：
[2, 3]
# stack contains indeces (0 and 1 have been popped)
對應元素：
[3, 2]
# ... of decreasing elements (... because 1 and 2 were smaller than 3)
其理由是，對于每一個元素x中a，你知道你可以完全忘記所有小先前的元素，你將永遠不會“闖過”x回頭看以后（如果有更小的元素比未來元素小，所以會當x！ ）。
您可以輕松驗證for-loop 是否有 n 次迭代。此外，可以看到while-loop 最多也有 n 次迭代（即使它是嵌套的），因為每個索引只能從堆疊中彈出一次。因此，整個演算法在時間和空間上都是線性的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/335902.html
上一篇：如何散列哈希表中的鍵
下一篇：字典序最小字串的排列數