最大化数组末位元素的最少操作次数

标签: 数组 枚举

难度: Medium

给你两个下标从 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 <= 1000
  • 1 <= nums1[i] <= 109
  • 1 <= nums2[i] <= 109

Submission

运行时间: 35 ms

内存: 16.4 MB

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        def f(last1: int, last2: int) -> int:
            res = 0
            for x, y in zip(nums1, nums2):
                if x > last1 or y > last2:
                    if y > last1 or x > last2:
                        return inf
                    res += 1
            return res
        ans = min(f(nums1[-1], nums2[-1]), f(nums2[-1], nums1[-1]))
        return ans if ans < inf else -1

Explain

这道题目的核心在于确保数组 nums1 的最后一个元素 nums1[n-1] 是整个 nums1 中的最大值。为此，我们可以选择交换 nums1[i] 和 nums2[i] （0 <= i < n-1）。题解的方法是定义一个辅助函数 f(last1, last2)，该函数用来计算若 nums1[n-1] 设为 last1，nums2[n-1] 设为 last2 时，使得 nums1[n-1] 是 nums1 中的最大值所需的最小交换次数。函数 f 遍历数组，对于每一对 nums1[i] 和 nums2[i]，若 nums1[i] 或 nums2[i] 大于 last1 或 last2，则可能需要进行交换。如果交换后仍无法满足条件，则返回无穷大（表示不可能通过交换达成条件）。最后，比较 f(nums1[-1], nums2[-1])（保持最后一对元素不变）和 f(nums2[-1], nums1[-1])（交换最后一对元素）的结果，取较小值。若结果为无穷大，则说明无法通过交换使 nums1[n-1] 成为最大值，返回 -1。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        def f(last1: int, last2: int) -> int:
            res = 0
            for x, y in zip(nums1, nums2):
                if x > last1 or y > last2:
                    if y > last1 or x > last2:
                        return inf  # 如果交换后仍然无法满足条件，返回无穷大
                    res += 1  # 统计需要交换的次数
            return res
        ans = min(f(nums1[-1], nums2[-1]), f(nums2[-1], nums1[-1]))  # 比较保持和交换最后一对元素的情况
        return ans if ans < inf else -1  # 如果最少操作次数是无穷大，则返回-1，否则返回操作次数

Explore

在函数`f`中，我们需要确保最终`nums1[n-1]`成为`nums1`数组中的最大值。这意味着，在任何位置`i`，`nums1[i]`或`nums2[i]`的值如果大于`last1`或`last2`，可能需要通过交换来避免这种情况，确保`last1`仍然是`nums1`中的最大值。直接确保`nums1[i] < last1`可能不足以处理所有情况，因为它忽略了`nums2[i]`可能成为`nums1[i]`的情况（通过交换），这样就可能需要更复杂的处理来维持`last1`作为最大值。因此，我们比较两个值对（`nums1[i]`与`last1`，`nums2[i]`与`last2`）来全面评估是否需要交换以维持最大值条件。

在函数`f`中，`if x > last1 or y > last2`条件用于检查在不进行交换的情况下，`nums1[i]`或`nums2[i]`是否有超过`last1`或`last2`的情况，这会威胁到`last1`成为`nums1`中的最大值的目标。如果在该条件成立的情况下，即使考虑交换后（`y > last1`或`x > last2`），这些值仍然大于`last1`或`last2`，则无论如何交换，都无法确保`last1`是`nums1`中的最大值。此时，返回无穷大表示这种情况下通过交换是无法达到使`last1`成为`nums1`中最大值的目标。

在Python中，无穷大可以通过`float('inf')`来表示，这是一个特殊的浮点数，表示正无穷大。使用`float('inf')`可以在比较操作中正常使用，如`inf > any real number`总是返回`True`，这保证了在涉及无穷大的比较时逻辑的正确性。在题解中，使用无穷大来标示无法通过交换达到条件的情况，同时在最后比较时，任何实数操作次数和无穷大比较，都会优先选择实数操作次数（如果存在的话）。