【LetMeFly】3194.最小元素和最大元素的最小平均值:排序
力扣题目链接:https://leetcode.cn/problems/minimum-average-of-smallest-and-largest-elements/
你有一个初始为空的浮点数数组 averages
。另给你一个包含 n
个整数的数组 nums
,其中 n
为偶数。
你需要重复以下步骤 n / 2
次:
- 从
nums
中移除 最小 的元素minElement
和 最大 的元素maxElement
。 - 将
(minElement + maxElement) / 2
加入到averages
中。
返回 averages
中的 最小 元素。
示例 1:
输入: nums = [7,8,3,4,15,13,4,1]
输出: 5.5
解释:
步骤 | 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] |
示例 2:
输入: nums = [1,9,8,3,10,5]
输出: 5.5
解释:
步骤 | 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] |
示例 3:
输入: nums = [1,2,3,7,8,9]
输出: 5.0
解释:
步骤 | nums | averages |
---|---|---|
0 | [1,2,3,7,8,9] | [] |
1 | [2,3,7,8] | [5] |
2 | [3,7] | [5,5] |
3 | [] | [5,5,5] |
提示:
2 <= n == nums.length <= 50
n
为偶数。1 <= nums[i] <= 50
解题方法:排序
二话不说对原始数组排个序,使用 i i i从 0 0 0到 l e n ( n u m s ) 2 − 1 \frac{len(nums)}2-1 2len(nums)−1遍历,更新 n u m s [ i ] + n u m s [ l e n ( n u m s ) − i − 1 ] nums[i]+nums[len(nums)-i-1] nums[i]+nums[len(nums)−i−1]的最小值。
遍历结束后,将最小值除以 2 2 2并返回。
- 时间复杂度 O ( n log n ) O(n\log n) O(nlogn)
- 空间复杂度 O ( log n ) O(\log n) O(logn)
AC代码
C++
class Solution {
public:
double minimumAverage(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 1000;
for (int i = 0; i < nums.size() / 2; i++) {
ans = min(ans, nums[i] + nums[nums.size() - i - 1]);
}
return 1. * ans / 2;
}
};
Go
package main
import "sort"
func minimumAverage(nums []int) float64 {
sort.Ints(nums)
ans := 1000
for i := 0; i < len(nums) / 2; i++ {
ans = min(ans, nums[i] + nums[len(nums) - i - 1])
}
return float64(ans) / 2
}
Java
import java.util.Arrays;
class Solution {
public double minimumAverage(int[] nums) {
Arrays.sort(nums);
int ans = 1000;
for (int i = 0; i < nums.length / 2; i++) {
ans = Math.min(ans, nums[i] + nums[nums.length - i - 1]);
}
return 1. * ans / 2;
}
}
Python
from typing import List
class Solution:
def minimumAverage(self, nums: List[int]) -> float:
nums.sort()
ans = 1000
for i in range(len(nums) // 2):
ans = min(ans, nums[i] + nums[-(i + 1)])
return ans / 2
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/142994095