You need to enable JavaScript to run this app. 有序列表存储元素的最优实现:优化Python代码解决大输入超时问题
优惠活动
大模型
产品
解决方案
定价
更多

有序列表存储元素的最优实现:优化Python代码解决大输入超时问题

原实现超时根因定位
  • 当前代码虽然通过二分查找定位插入位置,把查找过程优化到了O(logn)复杂度,但Python内置list是动态数组结构,insert操作需要将插入位置后的所有元素向后移动一位,单次插入的时间复杂度为O(n)。当任务规模N达到1e5及以上量级时,累计插入的总复杂度会达到O(N²),必然触发大输入用例的超时。
  • 逐行调用input()读取输入是另一个隐性的性能瓶颈,大输入下IO等待的开销会进一步放大超时问题。
分层优化方案

第一档:低改动成本的快速优化

  • 替换逐行输入逻辑:一次性读取全量输入拆分后处理,砍掉IO层面的额外开销,参考核心代码片段:
import sys
import bisect
data = sys.stdin.read().split()
ptr = 0
t = int(data[ptr])
ptr +=1
arr = []
for _ in range(t):
    op = data[ptr]
    ptr +=1
    if op == '1':
        p = int(data[ptr])
        ptr +=1
        # 用内置bisect模块的二分插入替代手写get_index,通过存负值实现降序维护
        bisect.insort(arr, -p)
    else:
        if len(arr) <3:
            print("Not enough enemies")
        else:
            pos = (len(arr)//3)-1
            print(-arr[pos])

注:这种方案依然保留了数组插入的O(n)移动开销,仅适合N规模较小的场景,无法解决超大输入下的核心超时问题。

第二档:大输入场景的最优实现(双堆结构方案)

针对“仅需查询全局第k大元素(k=当前总元素数//3)”的核心需求,完全不需要维护完整的有序数组,使用双堆结构可以将单次操作复杂度稳定在O(logn),彻底消除数组移动的开销:

  • 结构设计:
    • 最小堆top_k_heap:存储全局最大的k个元素,堆顶为这k个元素中的最小值,也就是需要查询的第k大目标值。
    • 最大堆rest_heap:存储剩余的所有元素,因为Python的heapq仅实现最小堆,存元素时将数值取反即可模拟最大堆效果。
  • 操作逻辑:
    1. 插入新元素P时:如果top_k_heap不为空且P大于等于其堆顶值,就将P压入top_k_heap;否则将P压入rest_heap。
    2. 每次插入完成后,计算当前总元素数cnt = len(top_k_heap) + len(rest_heap),目标值k = cnt//3。
    3. 动态调整两个堆的大小,保证len(top_k_heap) ==k:
      • 若len(top_k_heap) >k:弹出top_k_heap的堆顶元素,将其压入rest_heap。
      • 若len(top_k_heap) <k:弹出rest_heap的堆顶元素,将其压入top_k_heap。
    4. 执行查询操作时:若总元素数<3直接输出提示文案,否则直接返回top_k_heap的堆顶值即可,无需额外排序或遍历。
  • 参考实现代码:
import sys
import heapq

def main():
    data = sys.stdin.read().split()
    ptr =0
    t = int(data[ptr])
    ptr +=1
    top_k_heap = [] # 最小堆,存储全局最大的k个元素
    rest_heap = [] # 最大堆,存储剩余元素,存值取反模拟效果
    cnt =0
    output = []
    for _ in range(t):
        op = data[ptr]
        ptr +=1
        if op == '1':
            p = int(data[ptr])
            ptr +=1
            cnt +=1
            # 按规则插入元素
            if top_k_heap and p >= top_k_heap[0]:
                heapq.heappush(top_k_heap, p)
            else:
                heapq.heappush(rest_heap, -p)
            # 动态调整堆大小匹配当前k值
            k = cnt //3
            while len(top_k_heap) > k:
                val = heapq.heappop(top_k_heap)
                heapq.heappush(rest_heap, -val)
            while len(top_k_heap) <k:
                val = -heapq.heappop(rest_heap)
                heapq.heappush(top_k_heap, val)
        else:
            if cnt <3:
                output.append("Not enough enemies")
            else:
                output.append(str(top_k_heap[0]))
    # 批量输出减少IO开销
    print('\n'.join(output))

if __name__ == "__main__":
    main()

这种方案的总时间复杂度为O(N logN),在1e6量级的任务规模下也能稳定通过时限,是当前需求下有序数据存储与查询的最优实现。


内容的提问来源于stack exchange,提问作者shaik moeed

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.31 08:06:05