Easy

题目描述

你有一个初始为空的浮点数数组 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
解释：
步骤 0: nums = [7,8,3,4,15,13,4,1], averages = []
步骤 1: nums = [7,8,3,4,13,4], averages = [8]
步骤 2: nums = [7,8,4,4], averages = [8,8]
步骤 3: nums = [7,4], averages = [8,8,6]
步骤 4: nums = [], averages = [8,8,6,5.5]
averages 中的最小元素是 5.5

示例 2：

输入：nums = [1,9,8,3,10,5]
输出：5.5

示例 3：

输入：nums = [1,2,3,7,8,9]
输出：5.0

约束：

  • 2 <= n == nums.length <= 50
  • n 是偶数
  • 1 <= nums[i] <= 50

提示：

  • 如果 nums 已排序，那么 averages 的元素为 (nums[i] + nums[n - i - 1]) / 2，其中 i < n / 2

解题思路

解题思路

这道题的核心是要理解操作过程：每次移除数组中的最小值和最大值，并计算它们的平均值。

方法一：直接模拟 我们可以直接按照题目描述进行模拟：每次找到当前数组的最小值和最大值，移除它们，计算平均值。重复 n/2 次后，返回所有平均值中的最小值。

方法二：排序优化（推荐） 通过观察可以发现，如果我们先对数组排序，那么第 i 次操作时：

  • 最小值就是 nums[i]
  • 最大值就是 nums[n-1-i]

这样我们就可以直接计算出所有的平均值，而不需要每次都查找和移除元素。具体来说：

  • 排序后，第一次操作取 nums[0] 和 nums[n-1]
  • 第二次操作取 nums[1] 和 nums[n-2]
  • 以此类推…

这种方法的时间复杂度主要由排序决定，为 O(n log n)，而直接模拟的方法每次都要查找最值，时间复杂度为 O(n²)。

我们采用排序的方法实现，代码更简洁且效率更高。

代码实现

class Solution {
public:
    double minimumAverage(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        double minAvg = DBL_MAX;
        
        for (int i = 0; i < n / 2; i++) {
            double avg = (nums[i] + nums[n - 1 - i]) / 2.0;
            minAvg = min(minAvg, avg);
        }
        
        return minAvg;
    }
};

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

public class Solution {
    public double MinimumAverage(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;
        double minAvg = double.MaxValue;
        
        for (int i = 0; i < n / 2; i++) {
            double avg = (nums[i] + nums[n - 1 - i]) / 2.0;
            minAvg = Math.Min(minAvg, avg);
        }
        
        return minAvg;
    }
}

var minimumAverage = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let minAvg = Number.MAX_VALUE;
    
    for (let i = 0; i < n / 2; i++) {
        const avg = (nums[i] + nums[n - 1 - i]) / 2;
        minAvg = Math.min(minAvg, avg);
    }
    
    return minAvg;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(1)

说明：

  • 时间复杂度：主要由排序操作决定，为 O(n log n)，后续的遍历操作为 O(n)
  • 空间复杂度：只使用了常数级别的额外空间，为 O(1)（不考虑排序时的栈空间）

相关题目