我已經撰寫了以下演算法作為Codility Flags的解決方案。這通過了正確性檢查，但是在大多數性能檢查中超時。
所述的這種復雜性應該是O(m**2)其中m在峰值數A和n是的長度A。但是，while potentialK > maxFlags回圈應該只執行直到找到滿足標準的合適數量的標志。我不確定如何進一步優化時間復雜度。
def solution(A):
peaks = []
distances = []
if len(A) == 1: return 0
for i in range(1, len(A) -1):
if A[i] > A[i-1] and A[i] > A[i 1]:
if len(distances) == 0:
distances.append(i)
else:
distances.append(i - peaks[-1])
peaks.append(i)
if len(peaks) == 0: return 0
if len(peaks) == 1: return 1
if len(peaks) == 2: return 2 if peaks[1] - peaks[0] >= 2 else 1
potentialK = len(peaks)
maxFlags = 0
while potentialK > maxFlags:
cumDistance = 0
flags = 0
firstFlag = True
for i in range(1, len(distances)):
cumDistance = distances[i]
if cumDistance >= potentialK:
if firstFlag:
flags = 2
firstFlag = False
else:
flags = 1
cumDistance = 0
if flags > maxFlags and flags == potentialK:
return flags
elif flags > maxFlags and potentialK > flags:
maxFlags = flags
potentialK -= 1
return maxFlags
uj5u.com熱心網友回復：
您的演算法是 O(n^2)，因為輸入中可能有 O(n) 個峰值。加速您的演算法依賴于您提前知道輸入大小的事實。
觀察到答案是區間 中的整數[1, ceil(sqrt(n))]。任何小于 1 的距離要求都意味著您不能放置任何標志。由于距離要求，您不能放置超過 ceil(sqrt(n)) 的標志，即使每個元素都以某種方式達到峰值（這是不可能的）。
因此，您可以進行的一項優化是您只需要檢查 O(sqrt(n))potentialK值。（您將此作為您自己問題的答案發布。）這會將運行時間降低到 O(n^(3/2))，因為 m 是 O(n)，這顯然足夠快以通過 Codility 的測驗，但是我認為運行時仍然可以改進（正確性也可以）。
我們可以再做一個觀察：
存在一個正整數 i 使得：
- 對于每個 j，使得 j 是一個小于 i 的正整數，我們可以放置 j 個至少相距 j 距離的標志，并且
- 對于每個 j，使得 j 是一個大于 i 的正整數，我們不能放置至少相距 j 距離的 j 個標志。
這使我們能夠使用二進制搜索：
import math
def does_distance_work(peaks, distance):
peak_count = 1
last_peak = peaks[0]
for i in range(len(peaks)):
if peaks[i] >= last_peak distance:
peak_count = 1
last_peak = peaks[i]
return peak_count >= distance
def solution(A):
# Get the indices of the peaks.
peaks = []
for i in range(1, len(A) - 1):
if A[i] > A[i - 1] and A[i] > A[i 1]:
peaks.append(i)
# Return 0 if no peaks.
if not peaks:
return 0
# Check maximum value.
if does_distance_work(peaks, math.ceil(math.sqrt(len(A)))):
return math.ceil(math.sqrt(len(A)))
# If neither of the above two checks apply, find the largest i (as specified above) using binary search.
low, high = 1, math.ceil(math.sqrt(len(A))) - 1
while low <= high:
mid = low (high - low) // 2
mid_valid_distance = does_distance_work(peaks, mid)
mid_plus_one_valid_distance = does_distance_work(peaks, mid 1)
if not mid_valid_distance:
high = mid
elif mid_plus_one_valid_distance:
low = mid 1
else:
return mid
# If we've reached this line, something has gone wrong.
return -1
它遞回到 O(log(sqrt(n)) 的深度，對于我們的二進制搜索的每次迭代，O(n) 作業。那么最終的運行時間是 O(n * log(sqrt(n)))，這應該（并且確實）通過了性能測驗。
uj5u.com熱心網友回復：
我設法優化它如下：
由于各個標志之間的距離必須 >= 標志的數量，我們知道標志的最大數量將是峰的最后一個元素的根 - 峰的第一個元素： sqrt(peaks[-1] - peaks[0])
然后我就能夠將 potentialK 的初始值更新為
potentialK = math.ceil(math.sqrt(peaks[-1] - peaks[0]))
這應該會大大減少外部 while 回圈的迭代次數。
import math
def solution(A):
peaks = []
distances = []
if len(A) == 1: return 0
for i in range(1, len(A) -1):
if A[i] > A[i-1] and A[i] > A[i 1]:
if len(distances) == 0:
distances.append(i)
else:
distances.append(i - peaks[-1])
peaks.append(i)
if len(peaks) == 0: return 0
if len(peaks) == 1: return 1
if len(peaks) == 2: return 2 if peaks[1] - peaks[0] >= 2 else 1
potentialK = math.ceil(math.sqrt(peaks[-1] - peaks[0]))
maxFlags = 0
while potentialK > maxFlags:
cumDistance = 0
flags = 0
firstFlag = True
for i in range(1, len(distances)):
cumDistance = distances[i]
if cumDistance >= potentialK:
if firstFlag:
flags = 2
firstFlag = False
else:
flags = 1
cumDistance = 0
if flags > maxFlags and flags == potentialK:
return flags
elif flags > maxFlags and potentialK > flags:
maxFlags = flags
potentialK -= 1
return maxFlags
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/400697.html