精品课程网站建设设计方案,西安外包公司有哪些,长沙微信交流群,文创产品设计思路题目 给定一个矩阵#xff0c;包含 N∗M 个整数#xff0c;和一个包含 K 个整数的数组。现在要求在这个矩阵中找一个宽度最小的子矩阵#xff0c;要求子矩阵包含数组中所有的整数。 输入描述: 第一行输入两个正整数N#xff0c;M#xff0c;表示矩阵大小。 接下来 N 行 M …题目 给定一个矩阵包含 N∗M 个整数和一个包含 K 个整数的数组。现在要求在这个矩阵中找一个宽度最小的子矩阵要求子矩阵包含数组中所有的整数。 输入描述: 第一行输入两个正整数NM表示矩阵大小。 接下来 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 参考代码
package RealTest;/*** ClassName jvzhen* Description TODO* Author 21916* Date 2024/3/18 20:50*/import java.util.*;public class jvzhen{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 findMinWidth(matrix, target); // 调用函数计算最小宽度System.out.println(result); // 输出结果}public static int findMinWidth(int[][] matrix, int[] target) {int N matrix.length; // 矩阵的行数int M matrix[0].length; // 矩阵的列数int minLen Integer.MAX_VALUE; // 初始化最小宽度为最大值for (int left 0; left M; left) { // 遍历矩阵的每一列作为子矩阵的左边界MapInteger, Integer targetMap new HashMap(); // 用于记录目标数组中每个元素出现的次数for (int num : target) {targetMap.put(num, targetMap.getOrDefault(num, 0) 1); // 统计目标数组中每个元素的出现次数}int count target.length; // 初始化目标数组中元素的个数for (int right left; right M; right) { // 从左边界开始向右遍历作为子矩阵的右边界for (int i 0; i N; i) { // 遍历每一行int num matrix[i][right]; // 获取当前位置的数值if (targetMap.containsKey(num)) { // 如果当前数值在目标数组中targetMap.put(num, targetMap.get(num) - 1); // 将该数值在targetMap中的计数减1if (targetMap.get(num) 0) { // 如果该数值的计数减为0count--; // 目标数组元素个数减1}}}if (count 0) { // 如果目标数组中所有元素都在子矩阵中出现minLen Math.min(minLen, right - left 1); // 更新最小宽度break;}}}return minLen Integer.MAX_VALUE ? -1 : minLen; // 返回最小宽度若找不到返回-1}
}
