使数组相等的最小开销

标签: 贪心 数组 二分查找 前缀和 排序

难度: Hard

给你两个下标从 0 开始的数组 nums 和 cost ，分别包含 n 个 正 整数。

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

  • 将 nums 中 任意 元素增加或者减小 1 。

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

请你返回使 nums 中所有元素 相等 的 最少 总开销。

示例 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 <= 105
  • 1 <= nums[i], cost[i] <= 106
  • 测试用例确保输出不超过 253-1。

Submission

运行时间: 64 ms

内存: 35.3 MB

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:

        total=sum(cost)
        s=0
        for n,ct in sorted(zip(nums,cost)):
            s+=ct
            if s>total//2:
                break
        return sum([abs(x-n)*y for x,y in zip(nums,cost)])

Explain

这个题解利用了"成本加权中位数"的概念来找到一个目标值，使得将所有数组元素变成这个值的总成本最小。首先通过对数组nums和cost的zip操作合并，然后根据nums值进行排序。排序后，计算累积成本直到超过总成本的一半，此时对应的nums中的值作为目标值最佳。最后，计算使所有nums元素变为此目标值的成本和。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:

        total = sum(cost)  # 计算总成本
        s = 0  # 初始化累积成本为0
        for n, ct in sorted(zip(nums, cost)):  # 对nums和cost的组合进行排序，然后遍历
            s += ct  # 更新累积成本
            if s > total // 2:  # 当累积成本超过总成本的一半时
                break  # 找到最佳目标值，终止循环
        return sum([abs(x - n) * y for x, y in zip(nums, cost)])  # 计算并返回将所有nums元素变为目标值n的总成本

Explore

成本加权中位数是一种考虑权重的中位数，其中权重是每个元素对目标值影响的重要性或成本。在这个问题中，数组中的每个元素nums[i]有一个相应的成本cost[i]。算法的目标是找到一个数值，使得将所有nums元素调整到这个数值的总成本最小。通过将元素和它们的成本结合起来考虑，然后排序并计算累积成本，直到这个累积值超过总成本的一半。这时候的nums元素值即为成本加权中位数，因为在该点，一半以上的成本集中在这个值及之前的值上，使得成本最小化。

在累积成本超过总成本的一半时，选定的`nums`值作为目标值可以最小化总变动成本。这是因为，在此点之前和之后的元素需要向这个点调整，而由于累积成本刚好超过一半，这保证了大部分的调整成本（即权重）都集中在距离这个目标值较近的数值上，从而减少了总调整成本。

排序的目的是为了按照值的顺序处理元素，从而可以逐步累加成本，并找到成本加权中位数。排序确保我们可以正确地计算出在哪一点累积成本超过总成本的一半，这是找到最佳目标值的关键。排序对算法的效率有影响，因为排序操作通常是O(n log n)的时间复杂度，这可能是整个算法中最耗时的部分，但它是实现这种最小化成本方法的必要步骤。

如果数组`nums`中的所有元素相等，题解的算法仍然有效且更为简化。因为所有元素已经相等，所以不需要任何调整，整个数组已经是关于任何成本加权中位数的最小开销状态。在这种情况下，算法在计算总成本之后，会立即发现所有元素已经处于目标值，因此返回的总成本将是零。