机试题——最小矩阵宽度

题目描述

给定一个矩阵，包含 N * M 个整数，和一个包含 K 个整数的数组。

现在要求在这个矩阵中找一个宽度最小的子矩阵，要求子矩阵包含数组中所有的整数。

输入描述

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

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

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

下一行包含 K 个整数，表示所需包含的数组，K 个整数可能存在重复数字。

所有输入数据小于1000。

输出描述

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

用例输入

2 5
1 2 2 3 1
2 3 2 3 2
3
1 2 3

2

我们需要找到一个子矩阵，包含数字 1、2 和 3，并且每个数字的频率都至少是它在数组中出现的次数。

当窗口的列范围为 [3, 4] 时：

窗口包括列：[3, 1] 和 [3, 2]，仍然包含数字 1、2 和 3。

2 5
1 1 3 2 3
1 3 2 3 4
3
1 1 4

5

解题思路

宽度最小，长度不限。其实就是找一个列区间。

1. 滑动窗口法：使用滑动窗口在矩阵的列中查找子矩阵，保证窗口内包含所有需要的数字。窗口宽度从小到大逐步尝试，以找到最小的有效宽度。

2. 具体步骤：

   • 对于每一行，记录每列的数字出现情况。
   • 维护一个滑动窗口，该窗口内的列包含所有需要的数字及其频率。随着窗口的扩大，检查该窗口是否满足条件。
   • 如果满足条件，尝试收缩窗口以找到最小宽度。

3. 最终结果：输出最小宽度，如果没有找到有效的子矩阵，输出 -1。

代码

#include <iostream>
#include <vector>
#include <map>
#include <climits>
#include <algorithm>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);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;map<int, int> re;  // 存储所需的数字及其频率for (int i = 0; i < k; ++i) {int num;cin >> num;re[num]++;}int min_width = INT_MAX;// 初始化最小宽度为最大值// i 为列区间的起始for (int i = 0; i < m; ++i) {map<int, int> cur;// 当前窗口内的数字频率int ok = 0;  // 当前窗口包含的满足条件的数字个数// 滑动窗口的右边界for (int j = i; j < m; ++j) {// 更新当前窗口的数字频率 把j列的数据加进去for (int t = 0; t < n; t++) {int num = matrix[t][j];if (re.count(num)) {cur[num]++;// 当数字的频率达到了要求的数量时if (cur[num] == re[num]) {ok++;}}}// 当前窗口包含所有需要的数字，更新最小宽度if (ok == re.size()) {min_width = min(min_width, j - i + 1);}}}// 输出结果if (min_width == INT_MAX) {cout << -1 << endl;}else {cout << min_width << endl;}
}