leetcode
leetcode 901 ~ 950
最小化舍入误差以满足目标

最小化舍入误差以满足目标

难度:

标签:

题目描述

代码结果

运行时间: 31 ms, 内存: 16.1 MB


/*
题目思路:
1. 首先计算所有价格的向下舍入总和。
2. 使用Java Stream处理浮点数的差值集合。
3. 使用PriorityQueue来管理这些差值集合,并根据目标数量调整误差值。
*/

import java.util.*;
import java.util.stream.*;

public class MinimizeRoundingErrorStream {
    public String minimizeError(String[] prices, int target) {
        int floorSum = IntStream.range(0, prices.length)
                .map(i -> (int) Math.floor(Double.parseDouble(prices[i])))
                .sum();
        PriorityQueue<Double> pq = new PriorityQueue<>();
        double totalDiff = IntStream.range(0, prices.length)
                .mapToDouble(i -> {
                    double num = Double.parseDouble(prices[i]);
                    double diff = num - Math.floor(num);
                    if (diff > 0) pq.add(diff);
                    return diff;
                })
                .sum();
        int needCeil = target - floorSum;
        if (needCeil < 0 || needCeil > pq.size()) {
            return "-1";
        }
        double error = 0;
        for (int i = 0; i < needCeil; i++) {
            error += pq.poll();
        }
        error += pq.stream().mapToDouble(d -> 1 - d).sum();
        return String.format("%.3f", error);
    }
}

解释

方法:

这个题解首先将每个价格字符串转换为浮点数,并分解为整数部分和小数部分。整数部分直接累加以计算所有价格的整数总和。而小数部分(如果大于0)被收集到一个列表中,这些是可以通过支付额外的费用(即向上舍入)来调整的部分。接着,题解检查目标值是否可达。如果目标值小于当前整数总和或大于整数总和加上可以调整的价格数量(也即小数部分列表长度),则返回'-1'表示无法达成目标。否则,将小数部分列表按从大到小排序,计算通过向上舍入最大的几个小数部分以最小化总舍入误差,直到达到目标值。最终,输出总误差,格式化为三位小数。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
题解中通过将价格分解为整数部分和小数部分,并对小数部分进行排序来最小化误差。这种方法的有效性基于什么理论或逻辑?
这种方法基于贪心算法的逻辑。贪心算法选择每一步的局部最优解,希望通过这种方式达到全局最优解。在本题中,通过选择最大的小数部分先进行向上舍入,可以尽量减少达到目标整数时的总舍入误差,因为较大的小数部分向上舍入带来的误差增加相对较小。这种方法试图通过最大限度地利用每次舍入的'价值',来最小化总误差。
🦆
为何在确定目标值可达性时,需要检查目标值是否在当前整数总和与整数总和加上可调整的价格数量之间?
这种检查是为了确认目标值是否在可能的范围内。整数总和代表了没有进行任何舍入操作时所有价格的总和。整数总和加上可调整的价格数量(即有小数部分的价格数)表示所有价格都进行向上舍入后的最大可能总和。如果目标值小于不进行舍入的最小值或者大于最大可能的舍入值,那么这个目标值就是不可达的,因为无论如何舍入,都无法精确达到目标值。
🦆
排序小数部分并向上舍入最大的几个小数以最小化舍入误差,这种方法在所有情况下都是最优的吗?存在哪些可能的例外情况?
虽然这种方法在很多情况下能够达到较好的效果,但并不是在所有情况下都是最优的。例如,如果小数部分的分布与目标舍入次数之间存在特定的模式,简单的贪心策略可能不会产生最小的总舍入误差。此外,这种方法假设每次向上舍入大的小数部分总是最佳选择,但在某些特殊组合下,可能会有其他舍入组合提供更小的误差。
🦆
计算舍入误差时,为什么选择先对小数部分列表求和后再进行加减操作,而不是直接在遍历时计算总误差?
这种计算方式是为了更精确和简化计算过程。通过先对小数部分进行排序和分类,可以更容易地管理哪些小数部分被向上舍入,哪些被保留。这样做可以在确定了需要向上舍入的小数个数后,直接计算出总的误差值。如果在遍历每个价格时直接计算总误差,会因为还未决定哪些小数部分需要向上舍入而复杂化问题,增加错误和计算复杂度。

相关问题