3194. 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 elementmaxElement
, fromnums
. - Add
(minElement + maxElement) / 2
toaverages
.
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] |
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
Solutions
Solution 1: Sorting
First, we sort the array $\textit{nums}$. Then, we start taking elements from both ends of the array, calculating the sum of the two elements, and taking the minimum value. Finally, we return the minimum value divided by 2 as the answer.
The time complexity is $O(n \log n)$, and the space complexity is $O(\log n)$, where $n$ is the length of the array $\textit{nums}$.
1 2 3 4 5 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 |
|