LeetCode 1792. Maximum Average Pass Ratio Python İle Çözüm

Leet Code'da bulunan 1792 numaralı Maximum Average Pass Ratio sorusunu Python ile çözdük.
00:00 Soruya İlk Bakış
00:50 1. Çözüm Yöntemi O((N+K)LOGN)
--------------------------------------------
Time Complexity
1. Initial Heap Construction:
The loop iterates over the classes array, which contains n elements (where n is the number of classes).
For each class:
The initial possible_inc is calculated in O(1)
heapq.heappush() is called, which takes O(logn)
Total time complexity for this phase: O(nlogn)
2. Extra Students Distribution:
The loop runs k times (where k is the number of extraStudents).
For each iteration:
heapq.heappop() takes O(logn)
Updating the class and calculating possible_inc are O(1)
heapq.heappush() takes O(logn)
Total time complexity for this phase: O(klogn)
3. Final Time Complexity:
Combining the two phases, the overall time complexity is:
O(nlogn)+O(klogn)=O((n+k)logn)
Space Complexity
1. Heap:
The heap stores one element for each class, so the space required is O(n)
2. Other Variables:
Variables like average, old_av, new_av, and possible_inc are scalars, requiring O(1) space.
3. Final Space Complexity:
The overall space complexity is: O(n)