Hard

题目描述

给你两个下标从 0 开始的数组 nums 和 cost，它们都由 n 个正整数组成。

你可以执行下面的操作任意次数：

  • 将数组 nums 中任意元素增加或者减少 1。

对第 i 个元素执行一次操作的开销是 cost[i]。

返回使数组中所有元素 相等 的 最小总开销。

示例 1：

输入：nums = [1,3,5,2], cost = [2,3,1,14]
输出：8
解释：我们可以执行以下操作使所有元素都等于 2 ：
- 将第 0 个元素增加 1 次，开销为 2 。
- 将第 1 个元素减少 1 次，开销为 3 。
- 将第 2 个元素减少 3 次，开销为 1 + 1 + 1 = 3 。
总开销为 2 + 3 + 3 = 8 。
可以证明无法以更小的开销使数组元素相等。

示例 2：

输入：nums = [2,2,2,2,2], cost = [4,2,8,1,3]
输出：0
解释：数组中所有元素已经相等，不需要执行操作。

提示：

  • n == nums.length == cost.length
  • 1 <= n <= 10^5
  • 1 <= nums[i], cost[i] <= 10^6
  • 生成的测试用例满足输出结果不超过 2^53 - 1

解题思路

这道题的核心思路是找到一个目标值，使得将所有数字调整为这个目标值的总代价最小。

有两种主要的解法思路：

方法一：带权中位数（推荐）

  • 关键洞察：最优的目标值必定是加权中位数。对于带权数组，加权中位数是指累计权重达到总权重一半的位置对应的值。
  • 首先将 (nums[i], cost[i]) 对按照 nums[i] 排序
  • 计算总权重的一半，然后从左到右累加权重，找到加权中位数
  • 计算将所有元素调整为加权中位数的总代价

方法二：三分搜索

  • 代价函数关于目标值是一个单峰凹函数（先递减后递增）
  • 可以使用三分搜索在 [min(nums), max(nums)] 范围内找到最优目标值
  • 但实现相对复杂，且常数较大

方法三：枚举所有可能值

  • 由于最优解必定在 nums 中的某个值，可以枚举所有 nums[i] 作为目标值
  • 计算每个目标值对应的总代价，取最小值
  • 时间复杂度较高，但思路简单

本题推荐使用加权中位数的方法，因为它有严格的数学证明且效率最高。

代码实现

class Solution {
public:
    long long minCost(vector<int>& nums, vector<int>& cost) {
        int n = nums.size();
        vector<pair<int, int>> pairs;
        
        for (int i = 0; i < n; i++) {
            pairs.push_back({nums[i], cost[i]});
        }
        
        sort(pairs.begin(), pairs.end());
        
        long long totalCost = 0;
        for (int i = 0; i < n; i++) {
            totalCost += cost[i];
        }
        
        long long prefixCost = 0;
        int median = 0;
        for (int i = 0; i < n; i++) {
            prefixCost += pairs[i].second;
            if (prefixCost >= (totalCost + 1) / 2) {
                median = pairs[i].first;
                break;
            }
        }
        
        long long result = 0;
        for (int i = 0; i < n; i++) {
            result += (long long)abs(nums[i] - median) * cost[i];
        }
        
        return result;
    }
};

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        n = len(nums)
        pairs = list(zip(nums, cost))
        pairs.sort()
        
        total_cost = sum(cost)
        
        prefix_cost = 0
        median = 0
        for num, c in pairs:
            prefix_cost += c
            if prefix_cost >= (total_cost + 1) // 2:
                median = num
                break
        
        result = 0
        for i in range(n):
            result += abs(nums[i] - median) * cost[i]
        
        return result

public class Solution {
    public long MinCost(int[] nums, int[] cost) {
        int n = nums.Length;
        var pairs = new (int num, int cost)[n];
        
        for (int i = 0; i < n; i++) {
            pairs[i] = (nums[i], cost[i]);
        }
        
        Array.Sort(pairs, (a, b) => a.num.CompareTo(b.num));
        
        long totalCost = 0;
        foreach (int c in cost) {
            totalCost += c;
        }
        
        long prefixCost = 0;
        int median = 0;
        foreach (var (num, c) in pairs) {
            prefixCost += c;
            if (prefixCost >= (totalCost + 1) / 2) {
                median = num;
                break;
            }
        }
        
        long result = 0;
        for (int i = 0; i < n; i++) {
            result += (long)Math.Abs(nums[i] - median) * cost[i];
        }
        
        return result;
    }
}

var minCost = function(nums, cost) {
    const n = nums.length;
    const pairs = [];
    
    for (let i = 0; i < n; i++) {
        pairs.push([nums[i], cost[i]]);
    }
    
    pairs.sort((a, b) => a[0] - b[0]);
    
    const totalCost = cost.reduce((sum, c) => sum + c, 0);
    
    let prefixCost = 0;
    let median = 0;
    for (const [num, c] of pairs) {
        prefixCost += c;
        if (prefixCost >= Math.floor((totalCost + 1) / 2)) {
            median = num;
            break;
        }
    }
    
    let result = 0;
    for (let i = 0; i < n; i++) {
        result += Math.abs(nums[i] - median) * cost[i];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度加权中位数方法枚举方法
时间复杂度O(n log n)O(n²)
空间复杂度O(n)O(n)

相关题目