小鲸鱼的梦境
0%

『LeetCode』801 使序列递增的最小交换次数

发表于 分类于 Valine：
本文字数： 4k 阅读时长 ≈ 4 分钟

题目

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 <= 10^{5}
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 2 * 10^{5}

标签

数组, 动态规划

题解

【使序列递增的最小交换次数】简单动态规划的思路

动态规划

解析

对于数组中每个位置的数字，只有两种可能：交换 或 不交换，暴力解法枚举所有情况共有 \(2^n\) 种情况显然是不可能的，不难想到，这是动态规划中 01 背包的经典问题。

欲解决的问题可以概括为，求使得两数组满足严格单增的最小交换次数

对于动态规划，我们要思考它的子问题是什么，在这里显然是：求使得两数组前 \(n - 1\) 个位置满足严格单增的最小交换次数

要解决的问题已经很清晰了，现在假设子问题（使得两数组前 \(i - 1\) 个位置满足严格单增的最小交换次数）已经解出，接下来我们考虑如何由子问题转移到原问题，这里要分情况讨论

  • \(i - 1\) 执行了交换
  • \(i - 1\) 没有进行交换

分情况讨论的目的是为了保证数组能满足严格单增。所以到这里我们将最初的问题拆分成两个小的部分

  • 数组第 \(i\) 个位置执行交换的最小交换次数
  • 数组第 \(i\) 个位置不执行交换的最小交换次数
  • 注：如果某种情况下不能使得数组单增，我们可以将对应情况的最小交换次数设置为无穷大

定义符号

定义 \(dp[i][j]\)

  • \(i\) 表示两个数组第 \(i\) 个位置
  • \(j\) 只取 \(0\) 或 \(1\), 其中 \(0\) 表示第 \(i\) 个位置不交换，\(1\) 表示交换
  • \(dp[i][j]\) 表示保证两数组严格单调递增情况下第 \(i\) 个位置交换/不交换的最小交换次数
  • 初始化：下标为 0 的位置显然可以交换也可以不交换，所以 \(dp[0][0] = 0, dp[0][1] = 1\)
  • 注：如果交换/不交换不能使得数组严格单调递增的话，那么 \(dp[i][j]\) 设置为 0x7f7f7f7f 表示无穷大

状态转移方程

经历了上述思考，状态转移也容易想到了

\[ dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) \\ dp[i][1] = min(dp[i - 1][0]], dp[i - 1][1]) + 1 \]

注：方程中没有注明转移的条件，即转移后能满足两数组严格单增

最后，因为每一状态只与前一状态相关，我们只需维护两个变量分别表示 \(dp[i][0], dp[i][1]\)即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Code language: Python
class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
        # dp[i][j] 表示 第 i 个位置的,j = 0 - 交换 1 - 不交换 的最小交换次数
        pre1, pre2, x, y = -1, -1, 0, 0
        for i, j in zip(nums1, nums2):
            tmp1, tmp2 = 0x3f3f3f3f, 0x3f3f3f3f
            # 先考虑不交换的情况
            if i > pre1 and j > pre2 and x < tmp1:
                tmp1 = x
            if i > pre2 and j > pre1 and y < tmp1:
                tmp1 = y
            # 考虑交换的情况
            if j > pre1 and i > pre2 and x + 1 < tmp2:
                tmp2 = x + 1
            if j > pre2 and i > pre1 and y + 1 < tmp2:
                tmp2 = y + 1
            x, y, pre1, pre2 = tmp1, tmp2, i, j
        return min(x, y)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Code language: Java
class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int x = 0, y = 1;
        for (int i = 1; i < n; ++i) {
            int tmp = 0x3f3f3f3f, tmp2 = 0x3f3f3f3f;
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1] && x < tmp)
                tmp = x;
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1] && y < tmp)
                tmp = y;
            if (nums2[i] > nums1[i - 1] && nums1[i] > nums2[i - 1] && x + 1 < tmp2)
                tmp2 = x + 1;
            if (nums2[i] > nums2[i - 1] && nums1[i] > nums1[i - 1] && y + 1 < tmp2)
                tmp2 = y + 1;
            x = tmp;
            y = tmp2;
        }
        return Math.min(x, y);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Code language: C++
class Solution {
public:
    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        // dp[i][j] 表示 第 i 个位置的,j = 0 - 交换 1 - 不交换 的最小交换次数
        int n = nums1.size();
        int x = 0, y = 1;
        for (int i = 1; i < n; ++i) {
            // 先考虑不交换的情况
            int tmp = 0x3f3f3f3f;
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1] && x < tmp)
                tmp = x;
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1] && y < tmp)
                tmp = y;
            // 考虑交换的情况
            int tmp2 = 0x3f3f3f3f;
            if (nums2[i] > nums1[i - 1] && nums1[i] > nums2[i - 1] && x + 1 < tmp2)
                tmp2 = x + 1;
            if (nums2[i] > nums2[i - 1] && nums1[i] > nums1[i - 1] && y + 1 < tmp2)
                tmp2 = y + 1;
            x = tmp;
            y = tmp2;
        }
        return min(x, y);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* Code language: JavaScript */
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minSwap = function(nums1, nums2) {
    // dp[i][j] 表示 第 i 个位置的,j = 0 - 交换 1 - 不交换 的最小交换次数
    const n = nums1.length;
    let x = 0, y = 1;
    for (let i = 1; i < n; ++i) {
        // 先考虑不交换的情况
        let tmp = 0x3f3f3f3f;
        if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1] && x < tmp)
            tmp = x;
        if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1] && y < tmp)
            tmp = y;
        // 考虑交换的情况
        let tmp2 = 0x3f3f3f3f;
        if (nums2[i] > nums1[i - 1] && nums1[i] > nums2[i - 1] && x + 1 < tmp2)
            tmp2 = x + 1;
        if (nums2[i] > nums2[i - 1] && nums1[i] > nums1[i - 1] && y + 1 < tmp2)
            tmp2 = y + 1;
        x = tmp;
        y = tmp2;
    }
    return Math.min(x, y);
};
  • 时间复杂度: \(O(n)\)
  • 空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~