闯关leetcode——3194. Minimum Average of Smallest and Largest Elements

题目

地址

https://leetcode.com/problems/minimum-average-of-smallest-and-largest-elements/description/

内容

You have an array of floating point numbers averages which is initially empty. You are given an array nums of n integers where n is even.

You repeat the following procedure n / 2 times:

Remove the smallest element, minElement, and the largest element maxElement, from nums.
Add (minElement + maxElement) / 2 to averages.
Return the minimum element in averages.

Example 1:

Input: nums = [7,8,3,4,15,13,4,1]
Output: 5.5
Explanation:

step	nums	averages
0	[7,8,3,4,15,13,4,1]	[]
1	[7,8,3,4,13,4]	[8]
2	[7,8,4,4]	[8,8]
3	[7,4]	[8,8,6]
4	[]	[8,8,6,5.5]

The smallest element of averages, 5.5, is returned.

Example 2:

Input: nums = [1,9,8,3,10,5]
Output: 5.5
Explanation:

step	nums	averages
0	[1,9,8,3,10,5]	[]
1	[9,8,3,5]	[5.5]
2	[8,5]	[5.5,6]
3	[]	[5.5,6,6.5]

Example 3:

Input: nums = [1,2,3,7,8,9]
Output: 5.0
Explanation:

step	nums	averages
0	[1,2,3,7,8,9]	[]
1	[2,3,7,8]	[5]
2	[3,7]	[5,5]
3	[]	[5,5,5]

Constraints:

• 2 <= n == nums.length <= 50
• n is even.
• 1 <= nums[i] <= 50

解题

这题就是要从一个数组中不停去除最大最小数，算出它们的均值，然后取出这些均值中最小的均值并返回。
这种不停取出并去除最大最小数的问题，可以考虑使用优先队列。
我们设计两个堆：大顶堆和小顶堆，然后不停取出它们的top值。这样取出的就是最大数和最小数。

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;class Solution {
public:double minimumAverage(vector<int>& nums) {vector<double> result;priority_queue<int, vector<int>, greater<int>> pq;priority_queue<int, vector<int>, less<int>> pq2;for (int i = 0; i < nums.size(); i++) {pq.push(nums[i]);pq2.push(nums[i]);}for (int i = 0; i < nums.size() / 2; i++) {result.push_back((pq.top() + pq2.top()) / 2.0);pq.pop();pq2.pop();}return *min_element(result.begin(), result.end());}
};

代码地址

https://github.com/f304646673/leetcode/tree/main/3194-Minimum-Average-of-Smallest-and-Largest-Elements/cplusplus