DeepSeek LeetCode 2448.使数组相等的最小开销 public long minCost(int[] nums, int[] cost)

这道题是让所有数组元素变成同一个值时的最小总开销每个元素的变换成本是 |nums[i] - target| * cost[i]。核心思路这是一个带权中位数问题。· 最小化 ∑ cost[i] * |nums[i] - target|· 最优 target 是权值累积到中位数位置对应的 nums[i]推导假设把 nums 排序每个 (nums[i], cost[i]) 看作一个“质量”为 cost[i] 的点。目标找某个位置 target 使加权绝对距离最小。结论总 cost 的最小值在 target 取加权中位数时达到。加权中位数1. 按 nums 排序2. 累计 cost直到累计值 ≥ 总成本的一半3. 这个位置的 nums 就是 target为什么不是平均值绝对值函数的导数不连续加权中位数是使加权绝对偏差最小的点和平均数使平方和最小不同。算法步骤1. 将 (nums[i], cost[i]) 按 nums 排序2. 计算总成本 totalCost sum(cost)3. 从头累加 cost找到第一个累计 ≥ (totalCost 1)/2 的位置其 nums 即为 target4. 计算 ∑ cost[i] * |nums[i] - target|代码实现javapublic long minCost(int[] nums, int[] cost) {int n nums.length;Integer[] idx new Integer[n];for (int i 0; i n; i) idx[i] i;// 按 nums 排序Arrays.sort(idx, (a, b) - Integer.compare(nums[a], nums[b]));long totalCost 0;for (int c : cost) totalCost c;long half (totalCost 1) / 2;long accum 0;int target 0;// 找加权中位数for (int i 0; i n; i) {int id idx[i];accum cost[id];if (accum half) {target nums[id];break;}}// 计算最小开销long ans 0;for (int i 0; i n; i) {ans (long) Math.abs(nums[i] - target) * cost[i];}return ans;}时间复杂度O(n log n)排序占主导。思考为什么不是二分二分需要对 target 的导数进行分析这里目标函数是凸函数用三分查找也行但加权中位数直接 O(n log n) 更简洁。如果你想要三分查找或前缀和优化避免二次遍历的版本我也可以帮你写。