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))