最大平均通过率【LC1792】
一所学校里有一些班级,每个班级里有一些学生,现在每个班都会进行一场期末考试。给你一个二维数组
classes
,其中classes[i] = [passi, totali]
,表示你提前知道了第i
个班级总共有totali
个学生,其中只有passi
个学生可以通过考试。给你一个整数
extraStudents
,表示额外有extraStudents
个聪明的学生,他们 一定 能通过任何班级的期末考。你需要给这extraStudents
个学生每人都安排一个班级,使得 所有 班级的 平均 通过率 最大 。
一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。
请你返回在安排这 extraStudents
个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5
以内的结果都会视为正确结果。
- 思路:
- 首先添加每一个学生时,应使通过率的变化值最大,才能获得最大的平均通过率
- 实现时可以使用大顶堆存储一个二元组,内容各个班级的通过学生和总学生,堆以增加一个通过学生后,通过率的变化值从大到小排序。
- 这样堆顶元素即为添加一个学生通过率变化最大值对应的班级,操作
extraStudents
次,然后求得最终的平均通过率返回即可
- 实现
class Solution { public double maxAverageRatio(int[][] classes, int extraStudents) { PriorityQueue<double[]> pq = new PriorityQueue<double[]>((o1, o2) -> (o2[0] + 1) / (o2[1] + 1) - o2[0] / o2[1] > (o1[0] + 1) / (o1[1] + 1) - o1[0] / o1[1] ? 1 : -1 ); for (int[] c : classes){ pq.add(new double[]{c[0], c[1]}); } for (int i = 0; i < extraStudents; i++){ double[] c = pq.poll(); pq.add(new double[]{c[0] + 1, c[1] + 1}); } double res = 0; while (!pq.isEmpty()){ double[] c = pq.poll(); res += c[0] / c[1]; } return res / classes.length; } }
复杂度
- 时间复杂度:O(n+klogn),n 为班级数量,k 为必通过的学生人数,向堆中添加元素的时间复杂度为O ( l o g n )
- 空间复杂度:O ( n ) ,小顶堆的空间复杂度为O ( n )