最小矩阵宽度 - 华为OD统一考试（D卷）

OD统一考试（D卷）

分值： 200分

题解： Java / Python / C++

题目描述

给定一个矩阵，包含N*M个整数，和一个包含K个整数的数组。 现在要求在这个矩阵中找一个宽度最小的子短阵，要求子矩阵包含数组中所有的整数。

输入描述

第一行输入两个正整数 N, M 表示矩阵大小。

接下来 N 行 M列表示矩阵内容。

下一行包含一个正整数K。

下一行包含K个整数，表示所需包含的数组，K个整数可能存在重复数字， 所有输入数据小于 1000。

输出描述

输出包含一个整数，表示满足要求子矩阵的最小宽度，若找不到，输出-1.

示例1

输入：
2 5
1 2 2 3 1
2 3 2 3 2
3
1 2 3

输出：
2

说明：
短阵第0、3列包含了1、2、3，短阵第3、4列包含了1、2、3

示例2

输入：
2 5
1 2 2 3 1
1 3 2 3 4
3
1 1 4

输出：
5

说明：
短阵第1、2、3、4、5列包含了1、1、4

题解

这是一个滑动窗口类型的问题。

滑动窗口： 适用于解决连续子数组或子字符串的最优问题，例如最小子数组和、最长连续不重复子字符串等。通过滑动窗口，可以在线性时间内解决这些问题，而不需要使用暴力的穷举法。

具体解题思路如下：

1. 初始化两个指针 left 和 right，它们定义了一个滑动窗口，初始时窗口为空。
2. 遍历右指针 right，在每一步将当前右指针所在的列的所有元素加入一个哈希表 cntMap 中，记录每个元素的出现次数。
3. 当哈希表 cntMap 覆盖了目标哈希表 targetCntMap 时，说明当前窗口包含了数组中所有的整数，此时更新最小长度 ans，并将左指针 left 向右移动，缩小窗口。
4. 重复步骤 2 和 3，直到右指针 right 遍历完所有列。
5. 如果最小长度 ans 未被更新，则输出 -1；否则输出 ans。

这样可以通过滑动窗口的方式寻找满足要求子矩阵的最小宽度。在代码中，使用哈希表 cntMap 维护当前窗口的元素出现次数，通过左右指针的移动来不断调整窗口的大小。

Java

import java.util.HashMap;
import java.util.Scanner;
/**
 * @author code5bug
 */
class Main {

    /**
     * 计算满足要求子矩阵的最小宽度
     *
     * @param n            矩阵的行数
     * @param m            矩阵的列数
     * @param targetCntMap 目标数据hash计数
     * @param matrix       矩阵
     * @return 满足要求子矩阵的最小宽度，若找不到，输出-1
     */
    public static int solve(int n, int m, HashMap<Integer, Integer> targetCntMap, int[][] matrix) {
        HashMap<Integer, Integer> cntMap = new HashMap<>();
        int ans = Integer.MAX_VALUE;

        // 利用滑动窗口寻找满足要求子矩阵的最小宽度
        // 窗口大小 [left, right] 
        for (int left = 0, right = 0; right < m; right++) {
            // 将当前右指针 right 所在的列的所有元素加入哈希表 cntMap 中
            for (int row = 0; row < n; row++) cntMap.merge(matrix[row][right], 1, Integer::sum);

            // 当哈希表 cntMap 覆盖了哈希表 targetCntMap 时，更新最小长度 ans，并将左指针 left 向右移动缩小窗口（继续尝试寻找更小的矩阵宽度）
            while (mapCover(cntMap, targetCntMap)) {
                ans = Math.min(ans, right - left + 1);

                // 将当前左指针 left 所在的列的所有元素从哈希表 cntMap 中删除
                for (int k = 0; k < n; k++) cntMap.merge(matrix[k][left], -1, Integer::sum);

                left++;
            }
        }

        // 如果最小长度 ans 未被更新，则输出 -1；否则输出 ans
        return (ans == Integer.MAX_VALUE) ? -1 : ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        int k = sc.nextInt();  // 输入数组 t 的长度 k
        int[] t = new int[k];  // 用于存储数组 t 的一维数组
        HashMap<Integer, Integer> targetCntMap = new HashMap<>();
        // 读取数组 t 的元素，并将其存储到哈希表 targetCntMap 中
        for (int i = 0; i < k; i++) {
            t[i] = sc.nextInt();
            targetCntMap.merge(t[i], 1, Integer::sum);
        }

        int ans = sol