跳转至

3194. 最小元素和最大元素的最小平均值

题目描述

你有一个初始为空的浮点数数组 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]
返回 averages 中最小的元素，即 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

解法

方法一：排序

我们首先对数组 $\textit{nums}$ 进行排序，然后从数组的两端开始取元素，分别计算两个元素的和，取最小值。最后将最小值除以 2 作为答案返回即可。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1
2
3
4
5
class Solution:
    def minimumAverage(self, nums: List[int]) -> float:
        nums.sort()
        n = len(nums)
        return min(nums[i] + nums[-i - 1] for i in range(n // 2)) / 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
};

1
2
3
4
5
6
7
8
9
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
}

1
2
3
4
5
6
7
8
9
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;
}

1
2
3
4
5
6
7
8
impl Solution {
    pub fn minimum_average(mut nums: Vec<i32>) -> f64 {
        nums.sort();
        let n = nums.len();
        let ans = (0..n / 2).map(|i| nums[i] + nums[n - i - 1]).min().unwrap();
        ans as f64 / 2.0
    }
}

评论