题目描述

给定一个大小为 $N \times M$ 的矩阵，矩阵中的每个元素是一个整数。另外给定一个包含 $K$ 个整数的数组。要求在这个矩阵中找到一个宽度最小的子矩阵，使得这个子矩阵包含数组中所有的整数。如果找不到这样的子矩阵，输出 $-1$。

思路

这道题的核心思路是通过滑动窗口在矩阵的列上寻找一个最小的区间，使得该区间内的列包含目标数组中的所有整数。具体步骤是：首先统计目标数组中每个整数的频率，然后遍历矩阵的列，使用滑动窗口动态维护一个窗口内的整数频率，当窗口满足包含所有目标整数时，尝试缩小窗口以找到最小宽度。如果找不到满足条件的窗口，则返回 -1。

1. 问题分析:

   • 我们需要找到一个子矩阵，使得这个子矩阵的每一列至少包含数组中的所有整数。
   • 由于我们只关心列的宽度，因此可以将问题转化为在列上寻找一个最小的区间，使得这个区间内的列包含所有需要的整数。

2. 算法选择:

   • 我们可以使用滑动窗口的思想来解决这个问题。滑动窗口通常用于在一维数组中寻找满足某些条件的最小区间。
   • 在这个问题中，我们可以将每一列看作一个整体，然后在这些列上应用滑动窗口。

3. 具体步骤:

   • 首先，我们需要统计数组中每个整数的频率。
   • 然后，我们遍历矩阵的每一列，统计每一列中每个整数的频率。
   • 使用滑动窗口来寻找包含所有整数的最小区间。

cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>

using namespace std;

int minWidthSubmatrix(vector<vector<int>>& matrix, vector<int>& target) {
    int N = matrix.size();
    int M = matrix[0].size();
    int K = target.size();

    // 统计目标数组中每个整数的频率
    unordered_map<int, int> targetFreq;
    for (int num : target) {
        targetFreq[num]++;
    }

    int minWidth = INT_MAX;

    // 遍历所有可能的列区间
    for (int left = 0; left < M; ++left) {
        unordered_map<int, int> windowFreq;
        int count = 0;
        for (int right = left; right < M; ++right) {
            // 统计当前列中的整数频率
            for (int i = 0; i < N; ++i) {
                int num = matrix[i][right];
                if (targetFreq.find(num) != targetFreq.end()) {
                    windowFreq[num]++;
                    if (windowFreq[num] == targetFreq[num]) {
                        count++;
                    }
                }
            }

            // 如果当前窗口包含所有目标整数，则更新最小宽度
            while (count == targetFreq.size()) {
                minWidth = min(minWidth, right - left + 1);
                // 尝试缩小窗口
                for (int i = 0; i < N; ++i) {
                    int num = matrix[i][left];
                    if (targetFreq.find(num) != targetFreq.end()) {
                        windowFreq[num]--;
                        if (windowFreq[num] < targetFreq[num]) {
                            count--;
                        }
                    }
                }
                left++;
            }
        }
    }

    return minWidth == INT_MAX ? -1 : minWidth;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> matrix(N, vector<int>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> matrix[i][j];
        }
    }

    int K;
    cin >> K;
    vector<int> target(K);
    for (int i = 0; i < K; ++i) {
        cin >> target[i];
    }

    int result = minWidthSubmatrix(matrix, target);
    cout << result << endl;

    return 0;
}

python

def min_width_submatrix(matrix, target):
    N = len(matrix)
    M = len(matrix[0])
    K = len(target)

    # 统计目标数组中每个整数的频率
    target_freq = {}
    for num in target:
        target_freq[num] = target_freq.get(num, 0) + 1

    min_width = float('inf')

    # 遍历所有可能的列区间
    for left in range(M):
        window_freq = {}
        count = 0
        for right in range(left, M):
            # 统计当前列中的整数频率
            for i in range(N):
                num = matrix[i][right]
                if num in target_freq:
                    window_freq[num] = window_freq.get(num, 0) + 1
                    if window_freq[num] == target_freq[num]:
                        count += 1

            # 如果当前窗口包含所有目标整数，则更新最小宽度
            while count == len(target_freq):
                min_width = min(min_width, right - left + 1)
                # 尝试缩小窗口
                for i in range(N):
                    num = matrix[i][left]
                    if num in target_freq:
                        window_freq[num] -= 1
                        if window_freq[num] < target_freq[num]:
                            count -= 1
                left += 1

    return min_width if min_width != float('inf') else -1

# 读取输入
N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
K = int(input())
target = list(map(int, input().split()))

# 计算结果
result = min_width_submatrix(matrix, target)
print(result)

java

import java.util.*;

public class Main {
    public static int minWidthSubmatrix(int[][] matrix, int[] target) {
        int N = matrix.length;
        int M = matrix[0].length;
        int K = target.length;

        // 统计目标数组中每个整数的频率
        Map<Integer, Integer> targetFreq = new HashMap<>();
        for (int num : target) {
            targetFreq.put(num, targetFreq.getOrDefault(num, 0) + 1);
        }

        int minWidth = Integer.MAX_VALUE;

        // 遍历所有可能的列区间
        for (int left = 0; left < M; ++left) {
            Map<Integer, Integer> windowFreq = new HashMap<>();
            int count = 0;
            for (int right = left; right < M; ++right) {
                // 统计当前列中的整数频率
                for (int i = 0; i < N; ++i) {
                    int num = matrix[i][right];
                    if (targetFreq.containsKey(num)) {
                        windowFreq.put(num, windowFreq.getOrDefault(num, 0) + 1);
                        if (windowFreq.get(num).equals(targetFreq.get(num))) {
                            count++;
                        }
                    }
                }

                // 如果当前窗口包含所有目标整数，则更新最小宽度
                while (count == targetFreq.size()) {
                    minWidth = Math.min(minWidth, right - left + 1);
                    // 尝试缩小窗口
                    for (int i = 0; i < N; ++i) {
                        int num = matrix[i][left];
                        if (targetFreq.containsKey(num)) {
                            windowFreq.put(num, windowFreq.get(num) - 1);
                            if (windowFreq.get(num) < targetFreq.get(num)) {
                                count--;
                            }
                        }
                    }
                    left++;
                }
            }
        }

        return minWidth == Integer.MAX_VALUE ? -1 : minWidth;
    }

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

        int K = scanner.nextInt();
        int[] target = new int[K];
        for (int i = 0; i < K; ++i) {
            target[i] = scanner.nextInt();
        }

        int result = minWidthSubmatrix(matrix, target);
        System.out.println(result);
    }
}

题目内容

给定一个矩阵，包含 $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$