有序列表存储元素的最优实现:优化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仅实现最小堆,存元素时将数值取反即可模拟最大堆效果。
- 最小堆
- 操作逻辑:
- 插入新元素P时:如果
top_k_heap不为空且P大于等于其堆顶值,就将P压入top_k_heap;否则将P压入rest_heap。 - 每次插入完成后,计算当前总元素数
cnt = len(top_k_heap) + len(rest_heap),目标值k = cnt//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。
- 若
- 执行查询操作时:若总元素数<3直接输出提示文案,否则直接返回
top_k_heap的堆顶值即可,无需额外排序或遍历。
- 插入新元素P时:如果
- 参考实现代码:
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
相关产品推荐
相关产品推荐

