公司网站开发怎么做,门户网站建设会议纪要,建设小型网站系统开题报告,小县城做网站题目#xff1a; 对给定长度为N的非负整数序列A#xff0c;计算前奇数项的中位数。 输入#xff1a;首行表示序列长度N。次行为N个正整数A1至AN。 输出#xff1a;输出共(N1)/2行#xff08;向下取整#xff09;#xff0c;第i行表示到第A1...2i-1项…题目 对给定长度为N的非负整数序列A计算前奇数项的中位数。 输入首行表示序列长度N。次行为N个正整数A1至AN。 输出输出共(N1)/2行向下取整第i行表示到第A1...2i-1项的中位数。 暴力解法 n int(input()) a list(map(int, input().split())) b [] # 遍历输入序列的每个元素 for i in range(1, n 1): # 将当前元素添加到逐步增长的序列中 b.append(a[i - 1]) # 对逐步增长的序列进行排序以便后续找中位数 b.sort() # 当序列长度为奇数时输出当前的中位数 if i % 2 1: print(b[i // 2]) 最大最小堆
# heapq 模块它提供了堆操作的基本功能比如插入元素和删除最小元素。
import heapqn int(input())
a list(map(int, input().split()))
# 我们的目标是保持 max_heap 的大小比 min_heap 的大小大1这样 max_heap 的根节点就是中位数。
# 最大堆用于存储较小的一半数字最小堆存储较大的一半数字
max_heap, min_heap [], []for i in range(n):# 将数字加入到堆中# 如果 max_heap 为空或当前数字小于或等于 max_heap 的最大元素-max_heap[0] 是 max_heap 的最大元素因为我们用负数来模拟最大堆则将该数字插入 max_heap。否则将其插入 min_heap。if not max_heap or a[i] -max_heap[0]:heapq.heappush(max_heap, -a[i])else:heapq.heappush(min_heap, a[i])# 保持两个堆的大小平衡# 这两个循环确保了两个堆的大小保持平衡。如果 max_heap 的大小比 min_heap 的大小大2或更多就从 max_heap 中移除最大元素并将其插入 min_heap。如果 min_heap 的大小比 max_heap 的大小大就从 min_heap 中移除最小元素并将其插入 max_heap。while len(max_heap) len(min_heap) 1:heapq.heappush(min_heap, -heapq.heappop(max_heap))while len(min_heap) len(max_heap):heapq.heappush(max_heap, -heapq.heappop(min_heap))# 如果当前是奇数项输出中位数if i % 2 0:print(-max_heap[0])
