LeetCode 题解工作台
最大化数组末位元素的最少操作次数
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，这两个数组的长度都是 n 。 你可以执行一系列 操作（可能不执行） 。 在每次操作中，你可以选择一个在范围 [0, n - 1] 内的下标 i ，并交换 nums1[i] 和 nums2[i] 的值。 你的任务是找到满足以下条件所需的…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·结合·enumeration
答案摘要
我们可以分成两种情况讨论： 1. 不交换 $nums1[n - 1]$ 和 $nums2[n - 1]$ 的值
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·结合·enumeration 题型思路
题目描述
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，这两个数组的长度都是 n 。
你可以执行一系列 操作（可能不执行）。
在每次操作中，你可以选择一个在范围 [0, n - 1] 内的下标 i ，并交换 nums1[i] 和 nums2[i] 的值。
你的任务是找到满足以下条件所需的 最小 操作次数：
nums1[n - 1]等于nums1中所有元素的 最大值 ，即nums1[n - 1] = max(nums1[0], nums1[1], ..., nums1[n - 1])。nums2[n - 1]等于nums2中所有元素的 最大值 ，即nums2[n - 1] = max(nums2[0], nums2[1], ..., nums2[n - 1])。
以整数形式，表示并返回满足上述 全部 条件所需的 最小 操作次数，如果无法同时满足两个条件，则返回 -1 。
示例 1：
输入：nums1 = [1,2,7]，nums2 = [4,5,3] 输出：1 解释：在这个示例中，可以选择下标 i = 2 执行一次操作。 交换 nums1[2] 和 nums2[2] 的值，nums1 变为 [1,2,3] ，nums2 变为 [4,5,7] 。 同时满足两个条件。 可以证明，需要执行的最小操作次数为 1 。 因此，答案是 1 。
示例 2：
输入：nums1 = [2,3,4,5,9]，nums2 = [8,8,4,4,4] 输出：2 解释：在这个示例中，可以执行以下操作： 首先，选择下标 i = 4 执行操作。 交换 nums1[4] 和 nums2[4] 的值，nums1 变为 [2,3,4,5,4] ，nums2 变为 [8,8,4,4,9] 。 然后，选择下标 i = 3 执行操作。 交换 nums1[3] 和 nums2[3] 的值，nums1 变为 [2,3,4,4,4] ，nums2 变为 [8,8,4,5,9] 。 同时满足两个条件。 可以证明，需要执行的最小操作次数为 2 。 因此，答案是 2 。
示例 3：
输入：nums1 = [1,5,4]，nums2 = [2,5,3] 输出：-1 解释：在这个示例中，无法同时满足两个条件。 因此，答案是 -1 。
提示：
1 <= n == nums1.length == nums2.length <= 10001 <= nums1[i] <= 1091 <= nums2[i] <= 109
解题思路
方法一：分情况讨论 + 贪心
我们可以分成两种情况讨论：
- 不交换 和 的值
- 交换 和 的值
对于每一种情况，我们记数组 和 的最后一个值分别为 和 。然后遍历数组 和 的前 个值，用一个变量 记录交换次数。如果 且 ，则不需要交换，否则如果 且 ，则需要交换，否则无法同时满足两个条件，返回 。最后返回 即可。
我们记两种情况的交换次数分别为 和 ，如果 ，则无法同时满足两个条件，返回 ，否则返回 。
时间复杂度 ，其中 为数组长度。空间复杂度 。
class Solution:
def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
def f(x: int, y: int) -> int:
cnt = 0
for a, b in zip(nums1[:-1], nums2[:-1]):
if a <= x and b <= y:
continue
if not (a <= y and b <= x):
return -1
cnt += 1
return cnt
a, b = f(nums1[-1], nums2[-1]), f(nums2[-1], nums1[-1])
return -1 if a + b == -2 else min(a, b + 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for understanding of array manipulation with minimal operations.
- question_mark
Assess if the candidate considers edge cases like impossible swaps.
- question_mark
Check for the candidate's ability to choose an efficient approach in terms of swap order.
常见陷阱
外企场景- error
Forgetting to handle cases where no solution exists and returning -1 when necessary.
- error
Failing to optimize the number of swaps by not selecting the best indices.
- error
Overcomplicating the solution instead of focusing on the minimal operations needed.
进阶变体
外企场景- arrow_right_alt
Handling arrays with elements in descending or ascending order for a variety of swap conditions.
- arrow_right_alt
Dealing with larger arrays and considering performance optimizations.
- arrow_right_alt
Extending the problem to involve more than two arrays, requiring swaps across multiple arrays.