How does the greedy approach work for the "Minimum Cost to Make Arrays Identical"?

The greedy approach minimizes cost by focusing on sorting both arrays and calculating the differences step-by-step to ensure the cheapest transformations.

What is the key to solving this problem efficiently?

The key is sorting both arrays first, followed by applying a cost calculation based on the differences, ensuring the most efficient solution.

How does the problem handle rearranging subarrays?

Rearranging subarrays minimizes the cost by focusing on matching smaller values first, ensuring the least expensive changes are made first.

What is the time complexity of the solution?

The time complexity is O(n log n) due to the sorting step, which is the most time-consuming part of the solution.

Can negative numbers be part of the arrays in this problem?

Yes, negative numbers are allowed in both arrays, and the solution works efficiently with them by sorting and calculating the differences as usual.

#3424

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

将数组变相同的最小代价

给你两个长度都为 n 的整数数组 arr 和 brr 以及一个整数 k 。你可以对 arr 执行以下操作任意次：将 arr 分割成若干个连续的子数组，并将这些子数组按任意顺序重新排列。这个操作的代价为 k 。选择 arr 中的任意一个元素，将它增加或者减少一个正整数 x 。这个操作的代价为 …

数组贪心排序

题目描述

给你两个长度都为 n 的整数数组 arr 和 brr 以及一个整数 k 。你可以对 arr 执行以下操作任意次：

将 arr 分割成若干个 连续的 子数组，并将这些子数组按任意顺序重新排列。这个操作的代价为 k 。
选择 arr 中的任意一个元素，将它增加或者减少一个正整数 x 。这个操作的代价为 x 。

请你返回将 arr 变为 brr 的最小总代价。

子数组 是一个数组中一段连续非空的元素序列。

示例 1：

输入：arr = [-7,9,5], brr = [7,-2,-5], k = 2

输出：13

解释：

将 arr 分割成两个连续子数组：[-7] 和 [9, 5] 然后将它们重新排列成 [9, 5, -7] ，代价为 2 。
将 arr[0] 减小 2 ，数组变为 [7, 5, -7] ，操作代价为 2 。
将 arr[1] 减小 7 ，数组变为 [7, -2, -7] ，操作代价为 7 。
将 arr[2] 增加 2 ，数组变为 [7, -2, -5] ，操作代价为 2 。

将两个数组变相等的总代价为 2 + 2 + 7 + 2 = 13 。

示例 2：

输入：arr = [2,1], brr = [2,1], k = 0

输出：0

解释：

由于数组已经相等，不需要进行任何操作，所以总代价为 0 。

提示：

1 <= arr.length == brr.length <= 10⁵
0 <= k <= 2 * 10¹⁰
-10⁵ <= arr[i] <= 10⁵
-10⁵ <= brr[i] <= 10⁵

lightbulb

解题思路

方法一：贪心 + 排序

如果不允许对数组进行分割，那么我们可以直接计算两个数组的绝对差值之和，作为总代价 $c_1$ 。如果允许对数组进行分割，那么我们可以将数组 $\textit{arr}$ 分割成 $n$ 个长度为 1 的子数组，然后以任意顺序重新排列，然后与数组 $\textit{brr}$ 进行比较，计算绝对差值之和，作为总代价 $c_2$ ，要使得 $c_2$ 最小，我们可以将两个数组都排序，然后计算绝对差值之和。最终的结果为 $\min(c_1, c_2 + k)$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 $\textit{arr}$ 的长度。

1

2

3

4

5

6

7

8

class Solution:
    def minCost(self, arr: List[int], brr: List[int], k: int) -> int:
        c1 = sum(abs(a - b) for a, b in zip(arr, brr))
        arr.sort()
        brr.sort()
        c2 = k + sum(abs(a - b) for a, b in zip(arr, brr))
        return min(c1, c2)

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate recognize the greedy approach for minimizing costs?
question_mark
How efficiently do they handle the sorting step for large inputs?
question_mark
Do they understand how to minimize operations while ensuring correctness?

warning

常见陷阱

外企场景

error
Failing to recognize the importance of sorting both arrays first.
error
Incorrectly handling the cost calculation, especially when dealing with large differences.
error
Overcomplicating the solution with unnecessary operations, leading to higher costs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the arrays are already identical, how does the solution scale?
arrow_right_alt
How would the solution change if k were very large, pushing the problem towards near-linear time complexity?
arrow_right_alt
Can the approach handle edge cases with negative numbers or maximum array lengths efficiently?

help

常见问题

外企场景

继续练习

#3413 收集连续 K 个袋子可以获得的最多硬币数量 #3397 执行操作后不同元素的最大数量 #3457 吃披萨