尋求一些幫助來解決看似簡單的演算法。
簡要概述：我們有一個未排序的整數串列。目標是找出此串列的每個元素與最近的“0”值之間的距離。
因此，如果我們有一個類似于此的串列： [0, 1, 2, 0, 4, 5, 6, 7, 0, 5, 6, 9]
預期結果將是： [0, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3]
我試圖簡化問題以提出一些幼稚的演算法，但我無法弄清楚如何跟蹤前一個和下一個零值。我最初的想法是找出串列中零的所有索引并用值填充這些零之間的空白，但這顯然對我來說不太奏效。
執行不佳的代碼（到目前為止，我只是在倒數到下一個零的步驟）：
def get_empty_lot_index(arr: list) -> list:
''' Gets all indices of empty lots '''
lots = []
for i in range(len(arr)):
if arr[i] == 0:
lots.append(i)
return lots
def space_to_empty_lots(arr: list) -> list:
empty_lots = get_empty_lot_index(arr)
new_arr = []
start = 0
for i in empty_lots:
steps = i - start
while steps >= 0:
new_arr.append(steps)
steps -= 1
start = i 1
return new_arr
uj5u.com熱心網友回復：
一種可能的演算法是對輸入串列進行兩次掃描：一次向前，一次向后。每次保留上次遇到的索引 0 并存盤差值。在第二次掃描中，取第一次掃描中存盤的最小值和新結果：
def space_to_empty_lots(arr: list) -> list:
result = []
# first sweep
lastZero = -len(arr)
for i, value in enumerate(arr):
if value == 0:
lastZero = i
result.append(i - lastZero)
# second sweep
lastZero = len(arr)*2
for i, value in reversed(list(enumerate(arr))):
if value == 0:
lastZero = i
result[i] = min(result[i], lastZero - i)
return result
注意：此函式假設輸入串列中至少有一個 0。不清楚當沒有 0 時函式應該做什么。在這種情況下，此實作將回傳一個值大于輸入串列長度的串列。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/362053.html
上一篇：是否可以通過小塊計算哈希？
下一篇：編程中的斷言代碼及其定義