class Solution {
public:
int minSwap(vector<int>& nums1, vector<int>& nums2) {
}
};
801. 使序列递增的最小交换次数
我们有两个长度相等且不为空的整型数组 nums1 和 nums2 。在一次操作中，我们可以交换 nums1[i] 和 nums2[i]的元素。
nums1 = [1,2,3,8] ， nums2 =[5,6,7,4] ，你可以交换 i = 3 处的元素，得到 nums1 =[1,2,3,4] 和 nums2 =[5,6,7,8] 。返回 使 nums1 和 nums2 严格递增 所需操作的最小次数 。
数组 arr 严格递增 且 arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1] 。
注意：
示例 1:
输入: nums1 = [1,3,5,4], nums2 = [1,2,3,7] 输出: 1 解释: 交换 A[3] 和 B[3] 后，两个数组如下: A = [1, 3, 5, 7] ， B = [1, 2, 3, 4] 两个数组均为严格递增的。
示例 2:
输入: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9] 输出: 1
提示:
2 <= nums1.length <= 105nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 2 * 105原站题解
javascript 解法, 执行用时: 80 ms, 内存消耗: 52.4 MB, 提交时间: 2023-10-25 23:14:21
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var minSwap = function(nums1, nums2) {
const n = nums1.length;
let a = 0, b = 1;
for (let i = 1; i < n; i++) {
let at = a, bt = b;
a = b = n;
if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
a = Math.min(a, at);
b = Math.min(b, bt + 1);
}
if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
a = Math.min(a, bt);
b = Math.min(b, at + 1);
}
}
return Math.min(a, b);
};
golang 解法, 执行用时: 120 ms, 内存消耗: 9 MB, 提交时间: 2023-10-25 23:13:58
func minSwap1(nums1, nums2 []int) int {
n := len(nums1)
// f[i][0/1] 表示让 nums1 和 nums2 的前 i 个数严格递增所需操作的最小次数
// 其中 f[i][0] 不交换 nums1[i] 和 nums2[i]，f[i][1] 交换 nums1[i] 和 nums2[i]
f := make([][2]int, n)
f[0][1] = 1
for i := 1; i < n; i++ {
f[i] = [2]int{n, n} // 答案不会超过 n，故初始化成 n 方便后面取 min
if nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i] {
f[i][0] = f[i-1][0]
f[i][1] = f[i-1][1] + 1
}
if nums2[i-1] < nums1[i] && nums1[i-1] < nums2[i] {
f[i][0] = min(f[i][0], f[i-1][1])
f[i][1] = min(f[i][1], f[i-1][0]+1)
}
}
return min(f[n-1][0], f[n-1][1])
}
func minSwap(nums1, nums2 []int) int {
n, notSwap, swap := len(nums1), 0, 1
for i := 1; i < n; i++ {
ns, s := n, n // 答案不会超过 n，故初始化成 n 方便后面取 min
if nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i] {
ns, s = notSwap, swap+1
}
if nums2[i-1] < nums1[i] && nums1[i-1] < nums2[i] {
ns, s = min(ns, swap), min(s, notSwap+1)
}
notSwap, swap = ns, s
}
return min(notSwap, swap)
}
func min(a, b int) int { if a > b { return b }; return a }
cpp 解法, 执行用时: 148 ms, 内存消耗: 88.4 MB, 提交时间: 2023-10-25 23:13:28
class Solution {
public:
int minSwap1(vector<int> &nums1, vector<int> &nums2) {
// f[i][0/1] 表示让 nums1 和 nums2 的前 i 个数严格递增所需操作的最小次数
// 其中 f[i][0] 不交换 nums1[i] 和 nums2[i]，f[i][1] 交换 nums1[i] 和 nums2[i]
int n = nums1.size(), f[n][2];
memset(f, 0x3f, sizeof(f));
f[0][0] = 0, f[0][1] = 1;
for (int i = 1; i < n; i++) {
if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
f[i][0] = f[i - 1][0];
f[i][1] = f[i - 1][1] + 1;
}
if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
f[i][0] = min(f[i][0], f[i - 1][1]);
f[i][1] = min(f[i][1], f[i - 1][0] + 1);
}
}
return min(f[n - 1][0], f[n - 1][1]);
}
int minSwap(vector<int> &nums1, vector<int> &nums2) {
int n = nums1.size(), not_swap = 0, swap = 1;
for (int i = 1; i < n; ++i) {
int ns = n, s = n; // 答案不会超过 n，故初始化成 n 方便后面取 min
if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
ns = not_swap;
s = swap + 1;
}
if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
ns = min(ns, swap);
s = min(s, not_swap + 1);
}
not_swap = ns;
swap = s;
}
return min(not_swap, swap);
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 56.7 MB, 提交时间: 2023-10-25 23:13:01
class Solution {
public int minSwap1(int[] nums1, int[] nums2) {
// f[i][0/1] 表示让 nums1 和 nums2 的前 i 个数严格递增所需操作的最小次数
// 其中 f[i][0] 不交换 nums1[i] 和 nums2[i]，f[i][1] 交换 nums1[i] 和 nums2[i]
var n = nums1.length;
var f = new int[n][2];
f[0][1] = 1;
for (var i = 1; i < n; i++) {
f[i][0] = n; // 答案不会超过 n，故初始化成 n 方便后面取 min
f[i][1] = n;
if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
f[i][0] = f[i - 1][0];
f[i][1] = f[i - 1][1] + 1;
}
if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
f[i][0] = Math.min(f[i][0], f[i - 1][1]);
f[i][1] = Math.min(f[i][1], f[i - 1][0] + 1);
}
}
return Math.min(f[n - 1][0], f[n - 1][1]);
}
public int minSwap(int[] nums1, int[] nums2) {
int n = nums1.length, notSwap = 0, swap = 1;
for (var i = 1; i < n; ++i) {
int ns = n, s = n; // 答案不会超过 n，故初始化成 n 方便后面取 min
if (nums1[i - 1] < nums1[i] && nums2[i - 1] < nums2[i]) {
ns = notSwap;
s = swap + 1;
}
if (nums2[i - 1] < nums1[i] && nums1[i - 1] < nums2[i]) {
ns = Math.min(ns, swap);
s = Math.min(s, notSwap + 1);
}
notSwap = ns;
swap = s;
}
return Math.min(notSwap, swap);
}
}
python3 解法, 执行用时: 200 ms, 内存消耗: 32.1 MB, 提交时间: 2023-10-25 23:12:33
class Solution:
def minSwap2(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
# f[i][0/1] 表示让 nums1 和 nums2 的前 i 个数严格递增所需操作的最小次数
# 其中 f[i][0] 不交换 nums1[i] 和 nums2[i]，f[i][1] 交换 nums1[i] 和 nums2[i]
f = [[inf, inf] for _ in range(n)]
f[0] = [0, 1]
for i in range(1, n):
if nums1[i - 1] < nums1[i] and nums2[i - 1] < nums2[i]:
f[i][0] = f[i - 1][0]
f[i][1] = f[i - 1][1] + 1
if nums2[i - 1] < nums1[i] and nums1[i - 1] < nums2[i]:
f[i][0] = min(f[i][0], f[i - 1][1])
f[i][1] = min(f[i][1], f[i - 1][0] + 1)
return min(f[-1])
def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
not_swap, swap = 0, 1
for (a1, b1), (a2, b2) in pairwise(zip(nums1, nums2)): # 3.10 from itertools import pairwise
ns = s = inf
if a1 < a2 and b1 < b2:
ns, s = not_swap, swap + 1
if b1 < a2 and a1 < b2:
ns, s = min(ns, swap), min(s, not_swap + 1)
not_swap, swap = ns, s
return min(not_swap, swap)
java 解法, 执行用时: 13 ms, 内存消耗: 56.3 MB, 提交时间: 2023-10-25 23:11:02
class Solution {
public int minSwap(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length][2];
dp[0][0] = 0; dp[0][1] = 1;
for (int i = 1; i < nums1.length; i++) {
int a1 = nums1[i - 1], a2 = nums1[i], b1 = nums2[i - 1], b2 = nums2[i];
if ((a1 < a2 && b1 < b2) && (b1 < a2 && a1 < b2)) {
dp[i][0] = Math.min(dp[i - 1][0], dp[i - 1][1]); // 如果i【不互换】，则i-1可【互换】也可【不互换】
dp[i][1] = dp[i][0] + 1; // 如果i【互换】，则i-1可【互换】也可【不互换】
} else if (a1 < a2 && b1 < b2) {
dp[i][0] = dp[i - 1][0]; // 如果i【不互换】，则i-1必须【不互换】
dp[i][1] = dp[i - 1][1] + 1; // 如果i【互换】，则i-1必须【互换】
} else {
dp[i][0] = dp[i - 1][1]; // 如果i【不互换】，则i-1必须【互换】
dp[i][1] = dp[i - 1][0] + 1; // 如果i【互换】，则i-1必须【不互换】
}
}
return Math.min(dp[nums1.length - 1][0], dp[nums1.length - 1][1]);
}
}