在具有嵌套循环的未排序列表中搜索，因为需要保留索引位置

Question

我有一个列表 (stockData)，其中包含一些随机正整数，然后是另一个查询列表 (queries)，其中包含 stockData 中的一些位置（索引从 1 而不是 0 开始计算）。基于“查询”，代码必须识别比给定位置处的值更小的最接近值。如果出现碰撞/平局，则首选较小的索引位置。如果在 position 的两边都找不到这样的值，则应该返回 -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 我的代码工作正常，但执行时间太长。寻求任何优化它或任何其他纠正措施的帮助。谢谢 ！！我的代码：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现在可能对于给定的查询“day”，我需要找到相应的 sortedData[day] 并为所有较小的值找到最接近的索引？

Answer 1

stockData您可以通过保留一堆局部最小值来迭代您以获得最近的先前较小的值：

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

复杂性是O(n log(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))。