例如，如果串列是：[2,1,2,5,7,6,9]，則有 3 種可能的拆分方式：
[2,1,2] [5,7,6,9]
[2,1, 2,5] [7,6,9]
[2,1,2,5,7,6] [9]
我應該計算串列可以拆分多少次，以使左側的每個元素都小于右側的每個元素。因此，使用此串列，輸出將為 3。
這是我當前的解決方案：
def count(t):
c= 0
for i in range(len(t)):
try:
if max(t[:i]) < min(t[i:]):
c =1
except:
continue
return c
上面的代碼做了正確的事情，但它不是 O(n) 時間復雜度。我怎樣才能達到相同的結果，但速度更快？
uj5u.com熱心網友回復：
在線性時間內計算所有前綴最大值和后綴最小值。并在線性時間內將它們組合起來。
from itertools import accumulate as acc
from operator import lt
def count(t):
return sum(map(lt,
acc(t, max),
[*acc(t[:0:-1], min)][::-1]))
雅克要求一個基準：
1444.6 ms Jacques_Gaudin
5.0 ms Kelly_Bundy
1424.5 ms Jacques_Gaudin
4.4 ms Kelly_Bundy
1418.2 ms Jacques_Gaudin
4.7 ms Kelly_Bundy
代碼（在線試用！）：
from timeit import timeit
from itertools import accumulate as acc
from operator import lt
def Kelly_Bundy(t):
return sum(map(lt,
acc(t, max),
[*acc(t[:0:-1], min)][::-1]))
def Jacques_Gaudin(t):
if not t: return 0
v, left_max = list(t), max(t)
c, right_min = 0, left_max
while (item := v.pop()) and v:
if item == left_max:
left_max = max(v)
if item < right_min:
right_min = item
if left_max < right_min:
c = 1
return c
funcs = [
Jacques_Gaudin,
Kelly_Bundy,
]
t = list(range(12345))
for func in funcs * 3:
time = timeit(lambda: func(t), number=1)
print('%6.1f ms ' % (time * 1e3), func.__name__)
uj5u.com熱心網友回復：
我的嘗試：
def count(t):
max_el = t[0]
min_el = min(t[1:])
res = 0
for i in range(len(t)-1):
if t[i] == min_el:
min_el = min(t[i 1:])
if max_el < t[i]:
max_el = t[i]
if max_el < min_el:
res =1
return res
非常簡單，只有在可能不同時才計算最大值/最小值。
uj5u.com熱心網友回復：
這是我的最終答案：
def count(t):
c = 0
maxx = max(t)
right = [0]*len(t)
left = [0]*len(t)
maxx = t[0]
for i in range(0, len(t)):
if maxx >= t[i]:
left[i] = maxx
if maxx < t[i]:
maxx = t[i]
left[i] = maxx
minn = t[-1]
for i in range(len(t)-1,-1,-1):
if minn <= t[i]:
right[i] = minn
if minn > t[i]:
minn = t[i]
right[i] = minn
for i in range(0, len(t)-1):
if left[i] < right[i 1] :
c = 1
return c
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422779.html
標籤：
上一篇：將平面物件陣列轉換為嵌套物件