4.21网易算法笔试第1题第2题解答
第一题：定义一个最大堆，大于平均数就一直弹，每次当最大堆堆顶小于平均数的时候，就重新计算一次平均数，最后当堆顶数字等于平均数时结束循环
import heapq n = int(input()) nums = list(map(int, input().split())) def getRes(nums): heap = [-x for x in nums] heapq.heapify(heap) res = 0 while len(heap) > 1: top = heap[0] average = -sum(heap) / len(heap) if average == -heap[0]: break while -top > average: heapq.heappop(heap) top = heap[0] res += 1 return res print(getRes(nums))
第二题：并查集
n = int(input())
nums = list(map(int, input().split()))
parent = list(map(int, input().split()))
union_set = [-1 for _ in range(len(nums))]
for i in range(len(parent)):
union_set[i + 1] = parent[i]
def findfastparent(node):
if union_set[node - 1] == - 1:
return node
if nums[union_set[node - 1] - 1] >= nums[node - 1]:
return node
else:
node = union_set[node - 1]
return findfastparent(node)
res = []
for i in range(len(nums)):
ans = findfastparent(i + 1)
print(ans)
res.append(ans)
print(" ".join(res))