Medium

题目描述

给你两个下标从 0 开始的整数数组 nums1 和 nums2，两个数组的长度都是 n。

你可以执行一系列操作（可能不执行任何操作）。

在一次操作中，你可以选择一个下标 i（其中 0 <= i < n）并交换 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] <= 10^9
  • 1 <= nums2[i] <= 10^9

解题思路

这道题需要我们通过交换操作让两个数组的最后一个元素分别成为各自数组的最大值。

核心思路： 我们需要考虑两种情况：

  1. 不交换最后一对元素：此时 nums1[n-1] 和 nums2[n-1] 分别是两个数组的目标最大值
  2. 交换最后一对元素：此时 nums2[n-1] 和 nums1[n-1] 分别是两个数组的目标最大值

对于每种情况，我们遍历前 n-1 个元素，检查每个位置是否需要交换：

  • 如果 nums1[i] <= max1 且 nums2[i] <= max2，则不需要交换
  • 如果 nums1[i] <= max2 且 nums2[i] <= max1，则必须交换，操作数+1
  • 否则无解

算法步骤：

  1. 定义辅助函数计算给定目标最大值下的最少操作数
  2. 情况1：目标最大值为 (nums1[n-1], nums2[n-1])
  3. 情况2：目标最大值为 (nums2[n-1], nums1[n-1])，初始操作数为1
  4. 返回两种情况的最小值，如果都无解则返回-1

这种方法通过枚举所有可能的最终状态，确保找到最优解。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        
        auto calculate = [&](int max1, int max2) -> int {
            int operations = 0;
            for (int i = 0; i < n - 1; i++) {
                if (nums1[i] <= max1 && nums2[i] <= max2) {
                    // No swap needed
                } else if (nums1[i] <= max2 && nums2[i] <= max1) {
                    // Must swap
                    operations++;
                } else {
                    // No solution
                    return -1;
                }
            }
            return operations;
        };
        
        // Case 1: Don't swap the last pair
        int case1 = calculate(nums1[n-1], nums2[n-1]);
        
        // Case 2: Swap the last pair
        int case2 = calculate(nums2[n-1], nums1[n-1]);
        if (case2 != -1) case2++; // Add 1 for swapping the last pair
        
        if (case1 == -1 && case2 == -1) return -1;
        if (case1 == -1) return case2;
        if (case2 == -1) return case1;
        return min(case1, case2);
    }
};

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        
        def calculate(max1, max2):
            operations = 0
            for i in range(n - 1):
                if nums1[i] <= max1 and nums2[i] <= max2:
                    # No swap needed
                    pass
                elif nums1[i] <= max2 and nums2[i] <= max1:
                    # Must swap
                    operations += 1
                else:
                    # No solution
                    return -1
            return operations
        
        # Case 1: Don't swap the last pair
        case1 = calculate(nums1[n-1], nums2[n-1])
        
        # Case 2: Swap the last pair
        case2 = calculate(nums2[n-1], nums1[n-1])
        if case2 != -1:
            case2 += 1  # Add 1 for swapping the last pair
        
        if case1 == -1 and case2 == -1:
            return -1
        if case1 == -1:
            return case2
        if case2 == -1:
            return case1
        return min(case1, case2)

public class Solution {
    public int MinOperations(int[] nums1, int[] nums2) {
        int n = nums1.Length;
        
        int Calculate(int max1, int max2) {
            int operations = 0;
            for (int i = 0; i < n - 1; i++) {
                if (nums1[i] <= max1 && nums2[i] <= max2) {
                    // No swap needed
                } else if (nums1[i] <= max2 && nums2[i] <= max1) {
                    // Must swap
                    operations++;
                } else {
                    // No solution
                    return -1;
                }
            }
            return operations;
        }
        
        // Case 1: Don't swap the last pair
        int case1 = Calculate(nums1[n-1], nums2[n-1]);
        
        // Case 2: Swap the last pair
        int case2 = Calculate(nums2[n-1], nums1[n-1]);
        if (case2 != -1) case2++; // Add 1 for swapping the last pair
        
        if (case1 == -1 && case2 == -1) return -1;
        if (case1 == -1) return case2;
        if (case2 == -1) return case1;
        return Math.Min(case1, case2);
    }
}

var minOperations = function(nums1, nums2) {
    const n = nums1.length;
    
    function canMakeValid(max1, max2) {
        let operations = 0;
        for (let i = 0; i < n - 1; i++) {
            let valid = false;
            
            // Try without swapping
            if (nums1[i] <= max1 && nums2[i] <= max2) {
                valid = true;
            }
            
            // Try with swapping
            if (nums2[i] <= max1 && nums1[i] <= max2) {
                if (!valid) {
                    operations++;
                    valid = true;
                }
            }
            
            if (!valid) return -1;
        }
        return operations;
    }
    
    // Case 1: Don't swap the last elements
    let case1 = canMakeValid(nums1[n-1], nums2[n-1]);
    
    // Case 2: Swap the last elements
    let case2 = canMakeValid(nums2[n-1], nums1[n-1]);
    if (case2 !== -1) case2++;
    
    if (case1 === -1 && case2 === -1) return -1;
    if (case1 === -1) return case2;
    if (case2 === -1) return case1;
    
    return Math.min(case1, case2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

相关题目