Daily LeetCode – day0047 1619. Mean of Array After Removing Some Elements

import java.util.PriorityQueue;

// 1619. Mean of Array After Removing Some Elements
class Solution {
    public double trimMean(int[] arr) {
        int len = arr.length;
        int len5Percent = len / 20;
        PriorityQueue<Integer> biggest = new PriorityQueue<>();
        PriorityQueue<Integer> smallest = new PriorityQueue<>((Integer i1, Integer i2) -> i2 - i1);
        int sum = 0;
        for (int i = 0; i < len5Percent; ++i) {
            sum += arr[i];
            biggest.offer(arr[i]);
            smallest.offer(arr[i]);
        }
        for (int i = len5Percent; i < len; ++i) {
            sum += arr[i];
            if (arr[i] < smallest.peek()) {
                smallest.poll();
                smallest.offer(arr[i]);
            }
            if (arr[i] > biggest.peek()) {
                biggest.poll();
                biggest.offer(arr[i]);
            }
        }
        for (Integer i : biggest) {
            sum -= i;
        }
        for (Integer i : smallest) {
            sum -= i;
        }
        return sum / 18.0 / len5Percent;
    }
}
学习笔记:
这是一道数组的简单题,可以使用排序,但是时间复杂度比较高。
维护一个5%个元素的优先队列才是比较合理的做法。可惜这道简单题的数据太简单了,导致用优先队列做时间不但没减少,反而比一般得要多。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。