Easy

题目描述

给你一个整数数组 arr，请你删除最小 5% 的数字和最大 5% 的数字后，返回剩余数字的平均值。

与 标准答案 误差在 10^-5 的结果都被视为正确结果。

示例 1：

输入：arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]
输出：2.00000
解释：删除数组中最大和最小的元素后，所有的元素都等于2，所以平均值为2。

示例 2：

输入：arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
输出：4.00000

示例 3：

输入：arr = [6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,3,8,5,10,8,6,6,1,0,6,10,8,2,3,4]
输出：4.77778

提示：

  • 20 <= arr.length <= 1000
  • arr.length 是 20 的倍数
  • 0 <= arr[i] <= 10^5

解题思路

解题思路

这道题要求删除数组中最小的5%和最大的5%的元素后，计算剩余元素的平均值。

核心思路：

  1. 排序：首先对数组进行排序，这样最小的元素在前面，最大的元素在后面
  2. 计算删除数量：由于数组长度是20的倍数，5%就是 n/20 个元素
  3. 截取中间部分：删除前5%和后5%后，我们需要的是中间 90% 的元素
  4. 计算平均值：对剩余元素求和并除以元素个数

算法步骤：

  1. 对数组进行排序
  2. 计算需要删除的元素个数：removeCount = arr.length / 20
  3. 计算有效范围：从索引 removeCount 到 arr.length - removeCount - 1
  4. 对有效范围内的元素求和
  5. 返回平均值：sum / validCount

这是一个典型的排序+区间求和问题，时间复杂度主要由排序决定。

代码实现

class Solution {
public:
    double trimMean(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        int removeCount = n / 20;  // 5% of elements to remove from each end
        
        int sum = 0;
        int validCount = n - 2 * removeCount;
        
        for (int i = removeCount; i < n - removeCount; i++) {
            sum += arr[i];
        }
        
        return (double)sum / validCount;
    }
};

class Solution:
    def trimMean(self, arr: List[int]) -> float:
        arr.sort()
        n = len(arr)
        remove_count = n // 20  # 5% of elements to remove from each end
        
        # Calculate sum of middle 90% elements
        total = sum(arr[remove_count:n - remove_count])
        valid_count = n - 2 * remove_count
        
        return total / valid_count

public class Solution {
    public double TrimMean(int[] arr) {
        Array.Sort(arr);
        int n = arr.Length;
        int removeCount = n / 20;  // 5% of elements to remove from each end
        
        int sum = 0;
        int validCount = n - 2 * removeCount;
        
        for (int i = removeCount; i < n - removeCount; i++) {
            sum += arr[i];
        }
        
        return (double)sum / validCount;
    }
}

var trimMean = function(arr) {
    arr.sort((a, b) => a - b);
    const n = arr.length;
    const removeCount = n / 20;  // 5% of elements to remove from each end
    
    let sum = 0;
    const validCount = n - 2 * removeCount;
    
    for (let i = removeCount; i < n - removeCount; i++) {
        sum += arr[i];
    }
    
    return sum / validCount;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在排序上，其中 n 为数组长度
空间复杂度O(1)只使用常数个额外变量，原地排序