跳转至

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

题目描述

给你两个下标从 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

解法

方法一：分情况讨论 + 贪心

思考

最终要 \(nums1\) 的最大值在末尾、\(nums2\) 的最大值在末尾，且只能交换同下标。末尾一对要么保持、要么交换一次，两种终态决定了前面每一对应当如何摆放。

函数 \(f(x,y)\) 假定末尾已是 \((x,y)\)，对前 \(n-1\) 对：已满足则不动，对调后才满足则交换，否则无解。答案在「不换末尾」与「换末尾再加 \(1\)」中取可行的较小值。

我们可以分成两种情况讨论：

  1. 不交换 \(nums1[n - 1]\) 和 \(nums2[n - 1]\) 的值
  2. 交换 \(nums1[n - 1]\) 和 \(nums2[n - 1]\) 的值

对于每一种情况，我们记数组 \(nums1\) 和 \(nums2\) 的最后一个值分别为 \(x\) 和 \(y\)。然后遍历数组 \(nums1\) 和 \(nums2\) 的前 \(n - 1\) 个值，用一个变量 \(cnt\) 记录交换次数。如果 \(nums1[i] \leq x\) 且 \(nums2[i] \leq y\)，则不需要交换，否则如果 \(nums1[i] \leq y\) 且 \(nums2[i] \leq x\)，则需要交换，否则无法同时满足两个条件，返回 \(-1\)。最后返回 \(cnt\) 即可。

我们记两种情况的交换次数分别为 \(a\) 和 \(b\)，如果 \(a + b = -2\)，则无法同时满足两个条件，返回 \(-1\)，否则返回 \(\min(a, b + 1)\)。

时间复杂度 \(O(n)\)，其中 \(n\) 为数组长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    private int n;

    public int minOperations(int[] nums1, int[] nums2) {
        n = nums1.length;
        int a = f(nums1, nums2, nums1[n - 1], nums2[n - 1]);
        int b = f(nums1, nums2, nums2[n - 1], nums1[n - 1]);
        return a + b == -2 ? -1 : Math.min(a, b + 1);
    }

    private int f(int[] nums1, int[] nums2, int x, int y) {
        int cnt = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (nums1[i] <= x && nums2[i] <= y) {
                continue;
            }
            if (!(nums1[i] <= y && nums2[i] <= x)) {
                return -1;
            }
            ++cnt;
        }
        return cnt;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        auto f = [&](int x, int y) {
            int cnt = 0;
            for (int i = 0; i < n - 1; ++i) {
                if (nums1[i] <= x && nums2[i] <= y) {
                    continue;
                }
                if (!(nums1[i] <= y && nums2[i] <= x)) {
                    return -1;
                }
                ++cnt;
            }
            return cnt;
        };
        int a = f(nums1.back(), nums2.back());
        int b = f(nums2.back(), nums1.back());
        return a + b == -2 ? -1 : min(a, b + 1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func minOperations(nums1 []int, nums2 []int) int {
    n := len(nums1)
    f := func(x, y int) (cnt int) {
        for i, a := range nums1[:n-1] {
            b := nums2[i]
            if a <= x && b <= y {
                continue
            }
            if !(a <= y && b <= x) {
                return -1
            }
            cnt++
        }
        return
    }
    a, b := f(nums1[n-1], nums2[n-1]), f(nums2[n-1], nums1[n-1])
    if a+b == -2 {
        return -1
    }
    return min(a, b+1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function minOperations(nums1: number[], nums2: number[]): number {
    const n = nums1.length;
    const f = (x: number, y: number): number => {
        let cnt = 0;
        for (let i = 0; i < n - 1; ++i) {
            if (nums1[i] <= x && nums2[i] <= y) {
                continue;
            }
            if (!(nums1[i] <= y && nums2[i] <= x)) {
                return -1;
            }
            ++cnt;
        }
        return cnt;
    };
    const a = f(nums1.at(-1), nums2.at(-1));
    const b = f(nums2.at(-1), nums1.at(-1));
    return a + b === -2 ? -1 : Math.min(a, b + 1);
}

评论