关键词

PriorityQueue，堆

题目描述

https://leetcode.com/problems/mean-of-array-after-removing-some-elements/

Given an integer array arr, return the mean of the remaining integers after 
removing the smallest 5% and the largest 5% of the elements.

Answers within 10-5 of the actual answer will be considered accepted.

 

Example 1:

Input: arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]
Output: 2.00000
Explanation: After erasing the minimum and the maximum values of this array, 
all elements are equal to 2, so the mean is 2.
Example 2:

Input: arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
Output: 4.00000

博主提交的代码

class Solution {
    public double trimMean(int[] arr) {
        int offSet = (int)(arr.length * 0.05);
        double result = 0;
        Arrays.sort(arr);
        for(int i = offSet; i< arr.length - offSet;i++){
            result+=arr[i];
        }
        return result / (arr.length - offSet*2);
    }
}

其他人优秀的代码

https://leetcode.com/problems/mean-of-array-after-removing-some-elements/discuss/898764/Java-Iterating-Array-with-PriorityQueue-Beats-100

public double trimMean(int[] arr) {
    
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));
    int result = 0;
    int capacity = (int) Math.floor(arr.length * 0.05);
    
    //find the max and min
    for(int i = 0; i < arr.length; i ++) {
        //max 5%
        if(minHeap.size() < capacity) {
            minHeap.offer(arr[i]);
        }
        else if(minHeap.peek() < arr[i]){
            minHeap.poll();
            minHeap.offer(arr[i]);
        }
        //min 5%
        if(maxHeap.size() < capacity) {
            maxHeap.offer(arr[i]);
        }
        else if(maxHeap.peek() > arr[i]) {
            maxHeap.poll();
            maxHeap.offer(arr[i]);
        }
        
        result += arr[i];
    }
    
    //substract min & max
    while(!minHeap.isEmpty()) {
        result -= minHeap.poll();
    }
    while(!maxHeap.isEmpty()) {
        result -= maxHeap.poll();
    }
        
    return result / (double) (arr.length - capacity * 2);
}