题目描述
给你两个下标从 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
。
样例
输入: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。
输入: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。
输入: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
算法
(思维题) $O(n)$
- 一共只有两种情况:固定不动两个数组的最后一个数字;或交换两个数组的最后一个数字。
- 针对每种情况,遍历两个数组,如果某个位置上的数字不满足要求,且交换后也不满足要求,则返回无解。如果交换后满足要求,则答案累加 1。
- 以上两种情况求最小值就是答案。
时间复杂度
- 每种情况仅需要遍历数组一次,故总时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
const int INF = 1000000000;
class Solution {
private:
int solve(const vector<int>& nums1, const vector<int>& nums2) {
const int n = nums1.size();
int x = nums1.back(), y = nums2.back();
int ans = 0;
for (int i = 0; i < n - 1; i++) {
int a = nums1[i], b = nums2[i];
if (a <= x && b <= y)
continue;
if (b <= x && a <= y) ++ans;
else return INF;
}
return ans;
}
public:
int minOperations(vector<int>& nums1, vector<int>& nums2) {
int ans = solve(nums1, nums2);
swap(nums1.back(), nums2.back());
ans = min(ans, solve(nums1, nums2) + 1);
if (ans == INF)
return -1;
return ans;
}
};