class Solution {
public:
int minOperations(vector<int>& nums1, vector<int>& nums2) {
}
};
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 <= 10001 <= nums1[i] <= 1091 <= nums2[i] <= 109原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 6.5 MB, 提交时间: 2023-11-13 20:43:23
func minOperations(nums1, nums2 []int) int {
n := len(nums1)
f := func(last1, last2 int) (res int) {
for i, x := range nums1[:n-1] {
y := nums2[i]
if x > last1 || y > last2 {
if y > last1 || x > last2 {
return n + 1
}
res++
}
}
return
}
ans := min(f(nums1[n-1], nums2[n-1]), 1+f(nums2[n-1], nums1[n-1]))
if ans > n {
return -1
}
return ans
}
cpp 解法, 执行用时: 32 ms, 内存消耗: 42 MB, 提交时间: 2023-11-13 20:43:10
class Solution {
public:
int minOperations(vector<int> &nums1, vector<int> &nums2) {
auto f = [&](int last1, int last2) -> int {
int res = 0;
for (int i = 0; i + 1 < nums1.size(); i++) {
int x = nums1[i], y = nums2[i];
if (x > last1 || y > last2) {
if (y > last1 || x > last2) {
return nums1.size() + 1;
}
res++;
}
}
return res;
};
int ans = min(f(nums1.back(), nums2.back()), 1 + f(nums2.back(), nums1.back()));
return ans > nums1.size() ? -1 : ans;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 42.5 MB, 提交时间: 2023-11-13 20:42:58
class Solution {
public int minOperations(int[] nums1, int[] nums2) {
int n = nums1.length;
int ans = Math.min(f(nums1[n - 1], nums2[n - 1], nums1, nums2),
1 + f(nums2[n - 1], nums1[n - 1], nums1, nums2));
return ans > n ? -1 : ans;
}
private int f(int last1, int last2, int[] nums1, int[] nums2) {
int res = 0;
for (int i = 0; i + 1 < nums1.length; ++i) {
int x = nums1[i], y = nums2[i];
if (x > last1 || y > last2) {
if (y > last1 || x > last2) {
return nums1.length + 1;
}
res++;
}
}
return res;
}
}
python3 解法, 执行用时: 56 ms, 内存消耗: 16.3 MB, 提交时间: 2023-11-13 20:42:48
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