How do I minimize the cost to make all elements equal in the Minimum Cost to Make Array Equal problem?

By using binary search over the valid answer space, and leveraging prefix sums and a greedy approach to calculate the total transformation cost for each target value.

Why should I use binary search for this problem?

Binary search is used to efficiently find the optimal target value by narrowing down the possible candidates, reducing the overall computation time.

What makes the greedy approach necessary in this problem?

The greedy approach ensures that for each target value, the transformation costs are minimized by directly calculating the cost for each candidate value.

What are the most common mistakes in solving the Minimum Cost to Make Array Equal problem?

Common mistakes include overlooking that the target value should be one of the existing values in nums and not optimizing the cost calculation using prefix sums.

What is the role of the cost array in this problem?

The cost array determines how much it will cost to change each element of nums to the target value, and is crucial for computing the minimum transformation cost.

#2448

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

使数组相等的最小开销

给你两个下标从 0 开始的数组 nums 和 cost ，分别包含 n 个正整数。你可以执行下面操作任意次：将 nums 中任意元素增加或者减小 1 。对第 i 个元素执行一次操作的开销是 cost[i] 。请你返回使 nums 中所有元素相等的最少总开销。示例 1： …

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

题目描述

给你两个下标从 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 <= 10⁵
1 <= nums[i], cost[i] <= 10⁶
测试用例确保输出不超过 2⁵³-1。

lightbulb

解题思路

方法一：前缀和 + 排序 + 枚举

我们记数组 nums 所有元素为 $a_1, a_2, \cdots, a_n$ ，数组 cost 所有元素为 $b_1, b_2, \cdots, b_n$ 。我们不妨令 $a_1 \leq a_2 \leq \cdots \leq a_n$ ，即数组 nums 升序排列。

假设我们将数组 nums 中的元素全部变为 $x$ ，那么我们需要的总开销为：

\begin{aligned} \sum_{i=1}^{n} \left | a_i-x \right | b_i &= \sum_{i=1}^{k} (x-a_i)b_i + \sum_{i=k+1}^{n} (a_i-x)b_i \\ &= x\sum_{i=1}^{k} b_i - \sum_{i=1}^{k} a_ib_i + \sum_{i=k+1}^{n}a_ib_i - x\sum_{i=k+1}^{n}b_i \end{aligned}

其中 $k$ 为 $a_1, a_2, \cdots, a_n$ 中小于等于 $x$ 的元素个数。

我们可以使用前缀和的方法，计算 $\sum_{i=1}^{k} b_i$ 和 $\sum_{i=1}^{k} a_ib_i$ ，以及 $\sum_{i=k+1}^{n}a_ib_i$ 和 $\sum_{i=k+1}^{n}b_i$ 。

然后我们枚举 $x$ ，计算上述四个前缀和，得到上述的总开销，取其中的最小值即可。

时间复杂度 $O(n\times \log n)$ 。其中 $n$ 为数组 nums 的长度。主要是排序的时间复杂度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        arr = sorted(zip(nums, cost))
        n = len(arr)
        f = [0] * (n + 1)
        g = [0] * (n + 1)
        for i in range(1, n + 1):
            a, b = arr[i - 1]
            f[i] = f[i - 1] + a * b
            g[i] = g[i - 1] + b
        ans = inf
        for i in range(1, n + 1):
            a = arr[i - 1][0]
            l = a * g[i - 1] - f[i - 1]
            r = f[n] - f[i] - a * (g[n] - g[i])
            ans = min(ans, l + r)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should identify that binary search is essential for minimizing the cost by narrowing the search space to only valid targets.
question_mark
The solution should use efficient data structures like prefix sums to optimize the calculation of transformation costs.
question_mark
A deep understanding of greedy algorithms is expected to efficiently calculate the transformation cost for each target value.

warning

常见陷阱

外企场景

error
Failing to recognize that the target value should be one of the existing elements in nums, leading to incorrect or suboptimal solutions.
error
Not optimizing the calculation of transformation costs using prefix sums, resulting in slower solutions.
error
Overlooking the need to consider all potential target values and missing the most efficient transformation cost.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the nums array contains negative numbers or zeros? The approach would need to be adjusted to handle non-positive integers.
arrow_right_alt
What if the cost array allows for fractional costs? This could change the nature of the binary search and how costs are calculated.
arrow_right_alt
How would this problem scale if we had to handle multiple arrays or matrices, increasing the size of the input?

help

常见问题

外企场景

继续练习

#2389 和有限的最长子序列 #2271 毯子覆盖的最多白色砖块数 #2234 花园的最大总美丽值