机试题——最小矩阵宽度
题目描述
给定一个矩阵，包含 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。
代码
#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;
}
}