(C卷,200分)- 最小矩阵宽度（Java & JS & Python & C）

题目描述

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

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

输入描述

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

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

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

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

所有输入数据小于1000。

输出描述

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

用例

题目解析

本题其实就是“最小覆盖子串”问题的变形。关于最小覆盖子串问题，大家可以先看下：

当了解了最小覆盖子串问题后，本题中各个关键词可以类比到最小覆盖子串问题中的关键词：

因此，本题可以使用尺取法高效地求出满足要求地子矩阵地最小宽度。

尺取法在上面外链博客中，我做了详细说明，如果还不能够理解地话，可以继续看下这个博客：

华为OD机试 – 关联子串（Java & JS & Python & C）_华为od算法关联子串-CSDN博客

本题代码已添加详细注释说明，有疑问可以私信我。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  // 矩阵 [行数, 列数]
  const [n, m] = (await readline()).split(" ").map(Number);

  // 矩阵
  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix.push((await readline()).split(" ").map(Number));
  }

  // 目标数组长度
  const k = parseInt(await readline());

  // 目标数组
  const nums = (await readline()).split(" ").map(Number);

  // cnts[num] 记录的是 目标数组中num元素的个数
  const cnts = new Array(1000).fill(0);
  for (let num of nums) {
    cnts[num]++;
  }

  // 求解最小子矩阵宽度
  function getResult() {
    // 未完成匹配的元素的个数
    let total = k;

    // 记录最小子矩阵的宽度
    let minLen = Infinity;

    // 当前子矩阵的左边界（列号）
    let l = 0;
    // 当前子矩阵的右边界（列号）
    let r = 0;

    // 如果右边界未越界，则可以继续尝试找最小子矩阵
    while (r < m) {
      // 将第r列所有元素纳入子矩阵
      for (let i = 0; i < n; i++) {
        // 第r列的元素num
        const num = matrix[i][r];

        // cnts[num] 记录的是 目标数组中num元素的个数，也可以理解为：目标数组中num元素剩余未匹配的个数
        // 如果num不是目标数组元素，则cnts[num]初始时必然为0，对于非目标数组元素num, 即使进行了 cnts[num]--， 也不影响总的未匹配数量 total
        // 如果num是目标数组元素，则cnts[num]初始时必然大于0，且随着子矩阵扩大范围，如果子矩阵中包含num元素个数超过了初始cnts[num]数量，则超出部分起不到匹配效果，即不能影响总的未匹配数量
        if (cnts[num]-- > 0) {
          total--;
        }
      }

      // 纳入r列后，看看总的未匹配元素数量total还有几个，如果total为0，则说明当前子矩阵匹配到了所有目标数组元素
      while (total == 0) {
        // 若此时子矩阵宽度 r - l + 1 更小，则更新最小子矩阵宽度
        minLen = Math.min(minLen, r - l + 1);

        // 由于当前子矩阵已经匹配到所有目标数组元素，因此下一步应该将 l 右移，尝试更小宽度的子矩阵
        for (let i = 0; i < n; i++) {
          // l 右移，相当于当前子矩阵移除了第 l 列所有元素，被移除的元素num如果是目标数组元素，则对应的未匹配数量应该被恢复
          const num = matrix[i][l];

          // 如果当前num不是目标数组元素，或者当前num是目标数组元素，但是属于超出部分（这两种情况必然cnts[num] < 0），则对应num元素的恢复，不能影响到整体未匹配数量total，
          // 如果当前num是目标数组元素，且不是超出部分（此时必然cnts[num] >= 0），则对应num元素的恢复，会影响到整体未匹配数量total
          if (cnts[num]++ >= 0) {
            total++;
          }
        }

        // l右移，且下一轮要继续检查l右移后的子矩阵是否依旧能覆盖目标数组所有元素
        l++;
      }

      // r右移
      r++;
    }

    if (minLen == Infinity) {
      return -1;
    } else {
      return minLen;
    }
  }

  console.log(getResult());
})();

Java算法源码

import java.util.Scanner;

public class Main {
  static int n; // 矩阵行数
  static int m; // 矩阵列数
  static int[][] matrix; // 矩阵

  static int k; // 目标数组长度
  static int[] cnts; // cnts[num] 记录的是 目标数组中num元素的个数

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt();
    m = sc.nextInt();

    matrix = new int[n][m];

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = sc.nextInt();
      }
    }

    k = sc.nextInt();

    cnts = new int[1000];
    for (int i = 0; i < k; i++) {
      int num = sc.nextInt();
      cnts[num]++;
    }

    System.out.println(getResult());
  }

  public static int getResult() {
    // 未完成匹配的元素的个数
    int total = k;

    // 记录最小子矩阵的宽度
    int minLen = Integer.MAX_VALUE;

    // 当前子矩阵的左边界（列号）
    int l = 0;
    // 当前子矩阵的右边界（列号）
    int r = 0;

    // 如果右边界未越界，则可以继续尝试找最小子矩阵
    while (r < m) {

      // 将第r列所有元素纳入子矩阵
      for (int i = 0; i < n; i++) {
        // 第r列的元素num
        int num = matrix[i][r];
        // cnts[num] 记录的是 目标数组中num元素的个数，也可以理解为：目标数组中num元素剩余未匹配的个数
        // 如果num不是目标数组元素，则cnts[num]初始时必然为0，对于非目标数组元素num, 即使进行了 cnts[num]--， 也不影响总的未匹配数量 total
        // 如果num是目标数组元素，则cnts[num]初始时必然大于0，且随着子矩阵扩大范围，如果子矩阵中包含num元素个数超过了初始cnts[num]数量，则超出部分起不到匹配效果，即不能影响总的未匹配数量
        if (cnts[num]-- > 0) {
          total--;
        }
      }

      // 纳入r列后，看看总的未匹配元素数量total还有几个，如果total为0，则说明当前子矩阵匹配到了所有目标数组元素
      while (total == 0) {
        // 若此时子矩阵宽度 r - l + 1 更小，则更新最小子矩阵宽度
        minLen = Math.min(minLen, r - l + 1);

        // 由于当前子矩阵已经匹配到所有目标数组元素，因此下一步应该将 l 右移，尝试更小宽度的子矩阵
        for (int i = 0; i < n; i++) {
          // l 右移，相当于当前子矩阵移除了第 l 列所有元素，被移除的元素num如果是目标数组元素，则对应的未匹配数量应该被恢复
          int num = matrix[i][l];

          // 如果当前num不是目标数组元素，或者当前num是目标数组元素，但是属于超出部分（这两种情况必然cnts[num] < 0），
          //    则对应num元素的恢复，不能影响到整体未匹配数量total，
          // 如果当前num是目标数组元素，且不是超出部分（此时必然cnts[num] >= 0），则对应num元素的恢复，会影响到整体未匹配数量total
          if (cnts[num]++ >= 0) {
            total++;
          }
        }

        // l右移，且下一轮要继续检查l右移后的子矩阵是否依旧能覆盖目标数组所有元素
        l++;
      }

      // r右移
      r++;
    }

    if (minLen == Integer.MAX_VALUE) {
      return -1;
    } else {
      return minLen;
    }
  }
}

Python算法源码

import sys

# 输入获取
n, m = map(int, input().split())  # 矩阵 [行数, 列数]
matrix = [list(map(int, input().split())) for _ in range(n)]  # 矩阵
k = int(input())  # 目标数组长度
nums = list(map(int, input().split()))  # 目标数组

# cnts[num] 记录的是 目标数组中num元素的个数
cnts = [0] * 1000
for num in nums:
    cnts[num] += 1


# 算法入口
def getResult():
    # 未完成匹配的元素的个数
    total = k

    # 记录最小子矩阵的宽度
    minLen = sys.maxsize

    l = 0  # 当前子矩阵的左边界（列号）
    r = 0  # 当前子矩阵的右边界（列号）

    # 如果右边界未越界，则可以继续尝试找最小子矩阵
    while r < m:
        # 将第r列所有元素纳入子矩阵
        for i in range(n):
            #  第r列的元素numR
            numR = matrix[i][r]

            # cnts[numR] 记录的是 目标数组中numR元素的个数，也可以理解为：目标数组中numR元素剩余未匹配的个数
            # 如果numR不是目标数组元素，则cnts[numR]初始时必然为0，对于非目标数组元素numR, 即使进行了 cnts[numR]--， 也不影响总的未匹配数量 total
            # 如果numR是目标数组元素，则cnts[numR]初始时必然大于0，且随着子矩阵扩大范围，如果子矩阵中包含numR元素个数超过了初始cnts[numR]数量，则超出部分起不到匹配效果，即不能影响总的未匹配数量
            if cnts[numR] > 0:
                total -= 1
            cnts[numR] -= 1

        # 纳入r列后，看看总的未匹配元素数量total还有几个，如果total为0，则说明当前子矩阵匹配到了所有目标数组元素
        while total == 0:
            # 若此时子矩阵宽度 r - l + 1 更小，则更新最小子矩阵宽度
            minLen = min(minLen, r - l + 1)

            # 由于当前子矩阵已经匹配到所有目标数组元素，因此下一步应该将 l 右移，尝试更小宽度的子矩阵
            for i in range(n):
                # l 右移，相当于当前子矩阵移除了第 l 列所有元素，被移除的元素numL如果是目标数组元素，则对应的未匹配数量应该被恢复
                numL = matrix[i][l]

                # 如果当前numL不是目标数组元素，或者当前numL是目标数组元素，但是属于超出部分（这两种情况必然cnts[numL] < 0），则对应numL元素的恢复，不能影响到整体未匹配数量total，
                # 如果当前numL是目标数组元素，且不是超出部分（此时必然cnts[numL] >= 0），则对应numL元素的恢复，会影响到整体未匹配数量total
                if cnts[numL] >= 0:
                    total += 1
                cnts[numL] += 1

            # l右移，且下一轮要继续检查l右移后的子矩阵是否依旧能覆盖目标数组所有元素
            l += 1

        # r右移
        r += 1

    if minLen == sys.maxsize:
        return -1
    else:
        return minLen


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <limits.h>
#include <math.h>

#define MAX_SIZE 1000

// 矩阵行数, 矩阵列数
int n, m;
// 矩阵
int matrix[MAX_SIZE][MAX_SIZE];

// 目标数组长度
int k;
// cnts[num] 记录的是 目标数组中num元素的个数
int cnts[MAX_SIZE] = {0};

int getResult() {
    // 未完成匹配的元素的个数
    int total = k;

    // 记录最小子矩阵的宽度
    int minLen = INT_MAX;

    // 当前子矩阵的左边界（列号）
    int l = 0;
    // 当前子矩阵的右边界（列号）
    int r = 0;

    // 如果右边界未越界，则可以继续尝试找最小子矩阵
    while (r < m) {
        // 将第r列所有元素纳入子矩阵
        for (int i = 0; i < n; i++) {
            // 第r列的元素num
            int num = matrix[i][r];

            // cnts[num] 记录的是 目标数组中num元素的个数，也可以理解为：目标数组中num元素剩余未匹配的个数
            // 如果num不是目标数组元素，则cnts[num]初始时必然为0，对于非目标数组元素num, 即使进行了 cnts[num]--， 也不影响总的未匹配数量 total
            // 如果num是目标数组元素，则cnts[num]初始时必然大于0，且随着子矩阵扩大范围，如果子矩阵中包含num元素个数超过了初始cnts[num]数量，则超出部分起不到匹配效果，即不能影响总的未匹配数量
            if (cnts[num]-- > 0) {
                total--;
            }
        }

        // 纳入r列后，看看总的未匹配元素数量total还有几个，如果total为0，则说明当前子矩阵匹配到了所有目标数组元素
        while (total == 0) {
            // 若此时子矩阵宽度 r - l + 1 更小，则更新最小子矩阵宽度
            minLen = (int) fmin(minLen, r - l + 1);

            // 由于当前子矩阵已经匹配到所有目标数组元素，因此下一步应该将 l 右移，尝试更小宽度的子矩阵
            for (int i = 0; i < n; i++) {
                // l 右移，相当于当前子矩阵移除了第 l 列所有元素，被移除的元素num如果是目标数组元素，则对应的未匹配数量应该被恢复
                int num = matrix[i][l];

                // 如果当前num不是目标数组元素，或者当前num是目标数组元素，但是属于超出部分（这两种情况必然cnts[num] < 0），
                //    则对应num元素的恢复，不能影响到整体未匹配数量total，
                // 如果当前num是目标数组元素，且不是超出部分（此时必然cnts[num] >= 0），则对应num元素的恢复，会影响到整体未匹配数量total
                if (cnts[num]++ >= 0) {
                    total++;
                }
            }

            // l右移，且下一轮要继续检查l右移后的子矩阵是否依旧能覆盖目标数组所有元素
            l++;
        }

        // r右移
        r++;
    }

    if (minLen == INT_MAX) {
        return -1;
    } else {
        return minLen;
    }
}

int main() {
    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

    scanf("%d", &k);

    for (int i = 0; i < k; i++) {
        int num;
        scanf("%d", &num);
        cnts[num]++;
    }

    printf("%dn", getResult());

    return 0;
}