Welcome to Subscribe On Youtube
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 $\text{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 $\text{nums}$.
-
class Solution { public double minimumAverage(int[] nums) { Arrays.sort(nums); int n = nums.length; int ans = 1 << 30; for (int i = 0; i < n / 2; ++i) { ans = Math.min(ans, nums[i] + nums[n - i - 1]); } return ans / 2.0; } }
-
class Solution { public: double minimumAverage(vector<int>& nums) { sort(nums.begin(), nums.end()); int ans = 1 << 30, n = nums.size(); for (int i = 0; i < n; ++i) { ans = min(ans, nums[i] + nums[n - i - 1]); } return ans / 2.0; } };
-
class Solution: def minimumAverage(self, nums: List[int]) -> float: nums.sort() n = len(nums) return min(nums[i] + nums[n - i - 1] for i in range(n // 2)) / 2
-
func minimumAverage(nums []int) float64 { sort.Ints(nums) n := len(nums) ans := 1 << 30 for i, x := range nums[:n/2] { ans = min(ans, x+nums[n-i-1]) } return float64(ans) / 2 }
-
function minimumAverage(nums: number[]): number { nums.sort((a, b) => a - b); const n = nums.length; let ans = Infinity; for (let i = 0; i * 2 < n; ++i) { ans = Math.min(ans, nums[i] + nums[n - 1 - i]); } return ans / 2; }