最小化舍入误差以满足目标
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
题解中通过将价格分解为整数部分和小数部分,并对小数部分进行排序来最小化误差。这种方法的有效性基于什么理论或逻辑?
▷🦆
为何在确定目标值可达性时,需要检查目标值是否在当前整数总和与整数总和加上可调整的价格数量之间?
▷🦆
排序小数部分并向上舍入最大的几个小数以最小化舍入误差,这种方法在所有情况下都是最优的吗?存在哪些可能的例外情况?
▷🦆
计算舍入误差时,为什么选择先对小数部分列表求和后再进行加减操作,而不是直接在遍历时计算总误差?
▷