我有一個(gè)列表 (stockData)，其中包含一些隨機(jī)正整數(shù)，然后是另一個(gè)查詢(xún)列表 (queries)，其中包含 stockData 中的一些位置（索引從 1 而不是 0 開(kāi)始計(jì)算）?；凇安樵?xún)”，代碼必須識(shí)別比給定位置處的值更小的最接近值。如果出現(xiàn)碰撞/平局，則首選較小的索引位置。如果在 position 的兩邊都找不到這樣的值，則應(yīng)該返回 -1。例子一stockData = [5,6,8,4,9,10,8,3,6,4]queries = [6,5,4]At position 6 (index=5) in stockData, value is 10, both position 5 (index=4) and position 7 (index=6) are smaller values (9 and 8 resp.) than 10, hence we choose the one at a lesser position -> [5]At position 5 (index=4) in stockData, value is 9, position 4 (index=3) is smaller hence we choose position 4 -> [5,4]At position 4 (index=3) in stockData, value is 4, position 8 (index=7) is only value smaller hence we choose position 8 -> [5,4,8]Output[5,4,8]例子2stockData = [5,6,8,4,9,10,8,3,6,4]queries = [3,1,8]Here, at position 8, the value 3 is the smallest of the list, so we return -1Output[2,4,-1]約束條件1 <= n <= 10^5 (n is the length of stockData)1 <= stockData[i] <= 10^9 1 <= q <= 10^5 (q is the length of queries)1 <= queries[i] <= 10^9 我的代碼工作正常，但執(zhí)行時(shí)間太長(zhǎng)。尋求任何優(yōu)化它或任何其他糾正措施的幫助。謝謝 ?。∥业拇a：def predictAnswer(stockData, queries): # convert days to index query_idx = [val-1 for val in queries] # output_day_set out_day = [] for day in query_idx: min_price = stockData[day] day_found = False for i in range(1, max(day,len(stockData)-day)): prev = day-i nxt = day+i if prev >= 0 and stockData[prev] < min_price: out_day.append(prev+1) day_found = True break if nxt < len(stockData) and stockData[nxt] < min_price: out_day.append(nxt+1) day_found = True break if not day_found: out_day.append(-1) return out_day現(xiàn)在可能對(duì)于給定的查詢(xún)“day”，我需要找到相應(yīng)的 sortedData[day] 并為所有較小的值找到最接近的索引？
1 回答
月關(guān)寶盒
TA貢獻(xiàn)1772條經(jīng)驗(yàn) 獲得超5個(gè)贊
stockData您可以通過(guò)保留一堆局部最小值來(lái)迭代您以獲得最近的先前較小的值：
import heapq
class Data:
def __init__(self, day, value):
self.day = day
self.value = value
def __lt__(self, other):
return self.value >= other.value
def __repr__(self):
return f'Data(day={self.day}, value={self.value})'
def precalc(days):
result = []
heap = []
for day, value in days:
data = Data(day, value)
while heap and heap[0] < data:
heapq.heappop(heap)
result.append(heap[0].day if heap else -1)
heapq.heappush(heap, data)
return result
復(fù)雜性是O(n log(n))，因?yàn)槊刻熘荒芡扑?彈出一次。
要獲得預(yù)期的答案，您還必須在另一個(gè)方向上進(jìn)行：
def compare(f, b, q):
if f < 0: return b
if b < 0: return f
if q-f <= b-q:
return f
else:
return b
def predictAnswer(stockData, queries):
forward = precalc(enumerate(stockData, 1))
backward = list(reversed(precalc(reversed(list(enumerate(stockData, 1))))))
return [compare(forward[q-1], backward[q-1], q) for q in queries]
這還是O(n log(n))。