【2024年华为OD机试】 (C卷,200分)- 矩阵匹配（JavaScriptJava PythonC/C++）

一、问题描述

问题描述

给定一个大小为 ( N \times M )（( N \leq M )）的矩阵，从中选出 ( N ) 个数，要求任意两个数字不能在同一行或同一列。求选出来的 ( N ) 个数中第 ( K ) 大的数字的最小值。

输入描述

• 输入矩阵要求：( 1 \leq K \leq N \leq M \leq 150 )
• 输入格式：
  • 第一行：( N ) ( M ) ( K )
  • 接下来 ( N ) 行：( N \times M ) 矩阵

输出描述

• 输出从矩阵中选出的 ( N ) 个数中第 ( K ) 大的数字的最小值。

用例

输入

3 4 2
1 5 6 6
8 3 4 3
6 8 6 3

输出

3

解题思路

1. 问题分析

我们需要从矩阵中选出 ( N ) 个数，且这些数不能在同一行或同一列。然后在这些选出的数中找到第 ( K ) 大的数的最小值。

2. 二分图匹配

• 将矩阵的行和列分别看作二分图的两部分。
• 选择 ( N ) 个数且不重复行和列，相当于在二分图中找到一个匹配，匹配的边数至少为 ( N )。
• 我们需要找到这些匹配中第 ( K ) 大的数的最小值。

3. 二分法

• 使用二分法来枚举可能的第 ( K ) 大的数 ( kth )。
• 对于每个枚举的 ( kth )，检查矩阵中是否有至少 ( N - K + 1 ) 个数小于等于 ( kth )，并且这些数不在同一行或同一列。
• 如果满足条件，则尝试更小的 ( kth )；否则，尝试更大的 ( kth )。

4. 二分图最大匹配

• 对于每个 ( kth )，构建一个新的二分图，其中只包含矩阵中值小于等于 ( kth ) 的元素。
• 在这个新的二分图中，寻找最大匹配。如果最大匹配数大于等于 ( N - K + 1 )，则说明 ( kth ) 可能是一个候选值。

5. 二分法实现

• 初始化二分法的左右边界，左边界为矩阵中的最小值，右边界为矩阵中的最大值。
• 在每次迭代中，计算中间值 ( mid )，并检查是否满足条件。
• 根据检查结果调整左右边界，直到找到最小的 ( kth )。

总结

通过将问题转化为二分图匹配，并使用二分法来枚举可能的第 ( K ) 大的数，我们可以高效地找到满足条件的最小值。这种方法避免了暴力枚举，大大减少了计算量。

二、JavaScript算法源码

以下是对代码的详细注释和讲解，帮助你理解每一部分的逻辑和实现方式。

代码结构

1. 输入处理：读取输入的矩阵和参数。
2. 二分枚举：通过二分法枚举可能的第 ( K ) 大的最小值。
3. 检查函数：检查当前枚举的值是否满足条件。
4. DFS 实现二分图匹配：通过深度优先搜索（DFS）实现二分图的最大匹配。

详细注释和讲解

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

void (async function () {
  // 读取输入的第一行，解析出 N, M, K
  const [n, m, k] = (await readline()).split(" ").map(Number);

  // 初始化二分枚举的左右边界
  let min = 1; // 最小可能值
  let max = -Infinity; // 最大可能值，初始为负无穷

  // 读取矩阵
  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix.push((await readline()).split(" ").map(Number)); // 将每一行转换为数字数组
    max = Math.max(max, ...matrix[i]); // 更新最大值
  }

  // 二分枚举第 K 大的最小取值
  while (min <= max) {
    // mid 是被枚举出来的 N 个数中的第 K 大的最小取值
    const mid = (min + max) >> 1; // 取中间值，相当于 Math.floor((min + max) / 2)

    // 检查 mid 是否可以作为 N 个数中第 K 大的值
    if (check(mid)) {
      // 如果满足条件，尝试更小的值
      max = mid - 1;
    } else {
      // 如果不满足条件，尝试更大的值
      min = mid + 1;
    }
  }

  // 输出结果
  console.log(min);

  // 检查函数：判断当前枚举的 kth 是否满足条件
  function check(kth) {
    // 利用二分图最大匹配来求解，小于等于 kth 的元素个数（即二分图最大匹配）
    let smallerCount = 0;

    // 记录每个列号的匹配成功的行号
    // 初始时每个列号都处于未配对状态，此时将列号配对的行号赋值为 -1
    const match = new Array(m).fill(-1);

    // 遍历行号，每个行号对互相心仪的列号发起配对请求
    for (let i = 0; i < n; i++) {
      // 记录增广路访问过的列号
      const vis = new Array(m).fill(false);

      // 如果当前行号 i 可以找到匹配的列号，则 smallerCount + 1
      if (dfs(i, kth, match, vis)) {
        smallerCount++;
      }
    }

    // 判断是否满足条件：小于等于 kth 的元素个数是否 >= N - K + 1
    return smallerCount >= n - k + 1;
  }

  // DFS 实现二分图匹配
  function dfs(i, kth, match, vis) {
    // 行号 i 发起了配对请求

    // 遍历每一个列号 j
    for (let j = 0; j < m; j++) {
      // 如果当前列号 j 未被增广路探索过 && 当前行 i 列 j 的元素值 <= kth
      if (!vis[j] && matrix[i][j] <= kth) {
        vis[j] = true; // 标记列号 j 为已访问

        // 如果列号 j 未配对，或者已配对但可以找到其他行号重新配对
        if (match[j] == -1 || dfs(match[j], kth, match, vis)) {
          // 则当前行号 i 和列号 j 可以配对
          match[j] = i;
          return true;
        }
      }
    }

    // 如果找不到匹配的列号，返回 false
    return false;
  }
})();

代码逻辑详解

1. 输入处理

• 使用 readline 模块读取输入。
• 解析第一行得到 ( N )、( M )、( K )。
• 读取矩阵，并记录矩阵中的最大值 max，作为二分枚举的右边界。

2. 二分枚举

• 初始化二分枚举的左右边界：
  • min = 1：最小值从 1 开始。
  • max：矩阵中的最大值。
• 通过二分法枚举可能的第 ( K ) 大的最小值 mid。
• 调用 check(mid) 检查当前 mid 是否满足条件。

3. 检查函数 check(kth)

• 目标：检查是否存在至少 ( N - K + 1 ) 个小于等于 kth 的元素，并且这些元素不在同一行或同一列。
• 实现方式：
  • 使用二分图最大匹配算法。
  • 遍历每一行，尝试匹配一个列号。
  • 如果匹配成功，则 smallerCount + 1。
  • 最终判断 smallerCount 是否大于等于 ( N - K + 1 )。

4. DFS 实现二分图匹配

• 目标：为当前行号 i 找到一个匹配的列号 j。
• 实现方式：
  • 遍历所有列号 j。
  • 如果列号 j 未被访问过，并且矩阵中 matrix[i][j] <= kth，则尝试匹配。
  • 如果列号 j 未配对，或者已配对但可以找到其他行号重新配对，则匹配成功。
  • 返回匹配结果。

5. 输出结果

• 当二分枚举结束时，min 即为满足条件的最小值。

关键点总结

1. 二分枚举：通过二分法高效枚举可能的第 ( K ) 大的最小值。
2. 二分图匹配：将问题转化为二分图的最大匹配问题，确保选出的数不在同一行或同一列。
3. DFS 实现匹配：通过 DFS 实现二分图的匹配过程，确保匹配的列号满足条件。

通过以上注释和讲解，你应该能够理解代码的每一部分逻辑和实现方式。如果还有疑问，欢迎随时提出！

三、Java算法源码

代码结构

1. 输入处理：读取输入的矩阵和参数。
2. 二分枚举：通过二分法枚举可能的第 ( K ) 大的最小值。
3. 检查函数：检查当前枚举的值是否满足条件。
4. DFS 实现二分图匹配：通过深度优先搜索（DFS）实现二分图的最大匹配。

详细注释和讲解

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  // 定义全局变量
  static int n; // 矩阵的行数
  static int m; // 矩阵的列数
  static int k; // 第 K 大
  static int[][] matrix; // 存储矩阵

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

    // 读取输入的第一行，解析出 N, M, K
    n = sc.nextInt();
    m = sc.nextInt();
    k = sc.nextInt();

    // 初始化二分枚举的左右边界
    int min = 1; // 最小可能值
    int max = Integer.MIN_VALUE; // 最大可能值，初始为整型最小值

    // 读取矩阵
    matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = sc.nextInt(); // 读取矩阵元素
        max = Math.max(max, matrix[i][j]); // 更新最大值
      }
    }

    // 二分枚举第 K 大的最小取值
    while (min <= max) {
      // mid 是被枚举出来的 N 个数中的第 K 大的最小取值
      int mid = (min + max) >> 1; // 取中间值，相当于 (min + max) / 2

      // 检查 mid 是否可以作为 N 个数中第 K 大的值
      if (check(mid)) {
        // 如果满足条件，尝试更小的值
        max = mid - 1;
      } else {
        // 如果不满足条件，尝试更大的值
        min = mid + 1;
      }
    }

    // 输出结果
    System.out.println(min);
  }

  // 检查函数：判断当前枚举的 kth 是否满足条件
  public static boolean check(int kth) {
    // 利用二分图最大匹配来求解，小于等于 kth 的元素个数（即二分图最大匹配）
    int smallerCount = 0;

    // 记录每个列号的匹配成功的行号
    int[] match = new int[m];
    // 初始时每个列号都处于未配对状态，此时将列号配对的行号赋值为 -1
    Arrays.fill(match, -1);

    // 遍历行号，每个行号对互相心仪的列号发起配对请求
    for (int i = 0; i < n; i++) {
      // 记录增广路访问过的列号
      boolean[] vis = new boolean[m];

      // 如果当前行号 i 可以找到匹配的列号，则 smallerCount + 1
      if (dfs(i, kth, match, vis)) {
        smallerCount++;
      }
    }

    // 判断是否满足条件：小于等于 kth 的元素个数是否 >= N - K + 1
    return smallerCount >= n - k + 1;
  }

  // DFS 实现二分图匹配
  public static boolean dfs(int i, int kth, int[] match, boolean[] vis) {
    // 行号 i 发起了配对请求

    // 遍历每一个列号 j
    for (int j = 0; j < m; j++) {
      // 如果当前列号 j 未被增广路探索过 && 当前行 i 列 j 的元素值 <= kth
      if (!vis[j] && matrix[i][j] <= kth) {
        vis[j] = true; // 标记列号 j 为已访问

        // 如果列号 j 未配对，或者已配对但可以找到其他行号重新配对
        if (match[j] == -1 || dfs(match[j], kth, match, vis)) {
          // 则当前行号 i 和列号 j 可以配对
          match[j] = i;
          return true;
        }
      }
    }

    // 如果找不到匹配的列号，返回 false
    return false;
  }
}

代码逻辑详解

1. 输入处理

• 使用 Scanner 读取输入。
• 解析第一行得到 ( N )、( M )、( K )。
• 读取矩阵，并记录矩阵中的最大值 max，作为二分枚举的右边界。

2. 二分枚举

• 初始化二分枚举的左右边界：
  • min = 1：最小值从 1 开始。
  • max：矩阵中的最大值。
• 通过二分法枚举可能的第 ( K ) 大的最小值 mid。
• 调用 check(mid) 检查当前 mid 是否满足条件。

3. 检查函数 check(kth)

• 目标：检查是否存在至少 ( N - K + 1 ) 个小于等于 kth 的元素，并且这些元素不在同一行或同一列。
• 实现方式：
  • 使用二分图最大匹配算法。
  • 遍历每一行，尝试匹配一个列号。
  • 如果匹配成功，则 smallerCount + 1。
  • 最终判断 smallerCount 是否大于等于 ( N - K + 1 )。

4. DFS 实现二分图匹配

• 目标：为当前行号 i 找到一个匹配的列号 j。
• 实现方式：
  • 遍历所有列号 j。
  • 如果列号 j 未被访问过，并且矩阵中 matrix[i][j] <= kth，则尝试匹配。
  • 如果列号 j 未配对，或者已配对但可以找到其他行号重新配对，则匹配成功。
  • 返回匹配结果。

5. 输出结果

• 当二分枚举结束时，min 即为满足条件的最小值。

关键点总结

1. 二分枚举：通过二分法高效枚举可能的第 ( K ) 大的最小值。
2. 二分图匹配：将问题转化为二分图的最大匹配问题，确保选出的数不在同一行或同一列。
3. DFS 实现匹配：通过 DFS 实现二分图的匹配过程，确保匹配的列号满足条件。

通过以上注释和讲解，你应该能够理解代码的每一部分逻辑和实现方式。如果还有疑问，欢迎随时提出！

四、Python算法源码

以下是对 Python 代码的详细注释和讲解，帮助你理解每一部分的逻辑和实现方式。

代码结构

1. 输入处理：读取输入的矩阵和参数。
2. 二分枚举：通过二分法枚举可能的第 ( K ) 大的最小值。
3. 检查函数：检查当前枚举的值是否满足条件。
4. DFS 实现二分图匹配：通过深度优先搜索（DFS）实现二分图的最大匹配。

详细注释和讲解

import sys

# 输入获取
n, m, k = map(int, input().split())  # 读取 N, M, K
matrix = [list(map(int, input().split())) for _ in range(n)]  # 读取矩阵


# DFS 实现二分图匹配
def dfs(i, kth, match, vis):
    """
    为行号 i 找到一个匹配的列号 j。
    :param i: 当前行号
    :param kth: 当前枚举的第 K 大值
    :param match: 记录列号匹配的行号
    :param vis: 记录列号是否被访问过
    :return: 是否找到匹配
    """
    # 遍历每一个列号 j
    for j in range(m):
        # 如果列号 j 未被访问过，并且矩阵中 matrix[i][j] <= kth
        if not vis[j] and matrix[i][j] <= kth:
            vis[j] = True  # 标记列号 j 为已访问

            # 如果列号 j 未配对，或者已配对但可以找到其他行号重新配对
            if match[j] == -1 or dfs(match[j], kth, match, vis):
                # 则当前行号 i 和列号 j 可以配对
                match[j] = i
                return True

    # 如果找不到匹配的列号，返回 False
    return False


# 检查函数
def check(kth):
    """
    检查当前枚举的 kth 是否满足条件。
    :param kth: 当前枚举的第 K 大值
    :return: 是否满足条件
    """
    # 利用二分图最大匹配来求解，小于等于 kth 的元素个数（即二分图最大匹配）
    smallerCount = 0

    # 记录每个列号的匹配成功的行号
    # 初始时每个列号都处于未配对状态，此时将列号配对的行号赋值为 -1
    match = [-1] * m

    # 遍历行号，每个行号对互相心仪的列号发起配对请求
    for i in range(n):
        # 记录增广路访问过的列号
        vis = [False] * m

        # 如果当前行号 i 可以找到匹配的列号，则 smallerCount + 1
        if dfs(i, kth, match, vis):
            smallerCount += 1

    # 判断是否满足条件：小于等于 kth 的元素个数是否 >= N - K + 1
    return smallerCount >= n - k + 1


# 算法入口
def getResult():
    """
    主函数，通过二分枚举找到第 K 大的最小值。
    :return: 第 K 大的最小值
    """
    low = 1  # 二分枚举的左边界
    high = -sys.maxsize  # 二分枚举的右边界，初始为系统最小值

    # 找到矩阵中的最大值，作为二分枚举的右边界
    for i in range(n):
        for j in range(m):
            high = max(high, matrix[i][j])

    # 二分枚举第 K 大的最小取值
    while low <= high:
        # mid 是被枚举出来的 N 个数中的第 K 大的最小取值
        mid = (low + high) >> 1  # 取中间值，相当于 (low + high) // 2

        # 检查 mid 是否可以作为 N 个数中第 K 大的值
        if check(mid):
            # 如果满足条件，尝试更小的值
            high = mid - 1
        else:
            # 如果不满足条件，尝试更大的值
            low = mid + 1

    # 返回结果
    return low


# 算法调用
print(getResult())

代码逻辑详解

1. 输入处理

• 使用 input() 读取输入。
• 解析第一行得到 ( N )、( M )、( K )。
• 读取矩阵，并存储在 matrix 中。

2. 二分枚举

• 初始化二分枚举的左右边界：
  • low = 1：最小值从 1 开始。
  • high：矩阵中的最大值。
• 通过二分法枚举可能的第 ( K ) 大的最小值 mid。
• 调用 check(mid) 检查当前 mid 是否满足条件。

3. 检查函数 check(kth)

• 目标：检查是否存在至少 ( N - K + 1 ) 个小于等于 kth 的元素，并且这些元素不在同一行或同一列。
• 实现方式：
  • 使用二分图最大匹配算法。
  • 遍历每一行，尝试匹配一个列号。
  • 如果匹配成功，则 smallerCount + 1。
  • 最终判断 smallerCount 是否大于等于 ( N - K + 1 )。

4. DFS 实现二分图匹配

• 目标：为当前行号 i 找到一个匹配的列号 j。
• 实现方式：
  • 遍历所有列号 j。
  • 如果列号 j 未被访问过，并且矩阵中 matrix[i][j] <= kth，则尝试匹配。
  • 如果列号 j 未配对，或者已配对但可以找到其他行号重新配对，则匹配成功。
  • 返回匹配结果。

5. 输出结果

• 当二分枚举结束时，low 即为满足条件的最小值。

关键点总结

1. 二分枚举：通过二分法高效枚举可能的第 ( K ) 大的最小值。
2. 二分图匹配：将问题转化为二分图的最大匹配问题，确保选出的数不在同一行或同一列。
3. DFS 实现匹配：通过 DFS 实现二分图的匹配过程，确保匹配的列号满足条件。

五、C/C++算法源码：

以下是 C语言 和 C++ 版本的代码，并附带详细的中文注释和讲解。

C语言代码

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

#define MAX_SIZE 150

#define bool int
#define TRUE 1
#define FALSE 0

int n, m, k;
int matrix[MAX_SIZE][MAX_SIZE];

// DFS 实现二分图匹配
bool dfs(int i, int kth, int match[], int vis[]) {
    // 行号 i 发起了配对请求
    // 遍历每一个列号 j
    for (int j = 0; j < m; j++) {
        // 如果列号 j 未被访问过，并且矩阵中 matrix[i][j] <= kth
        if (!vis[j] && matrix[i][j] <= kth) {
            vis[j] = TRUE; // 标记列号 j 为已访问

            // 如果列号 j 未配对，或者已配对但可以找到其他行号重新配对
            if (match[j] == -1 || dfs(match[j], kth, match, vis)) {
                // 则当前行号 i 和列号 j 可以配对
                match[j] = i;
                return TRUE;
            }
        }
    }

    // 如果找不到匹配的列号，返回 FALSE
    return FALSE;
}

// 检查函数：判断当前枚举的 kth 是否满足条件
bool check(int kth) {
    // 利用二分图最大匹配来求解，小于等于 kth 的元素个数（即二分图最大匹配）
    int smallerCount = 0;

    // 记录每个列号的匹配成功的行号
    int match[m];
    // 初始时每个列号都处于未配对状态，此时将列号配对的行号赋值为 -1
    for (int i = 0; i < m; i++) match[i] = -1;

    // 遍历行号，每个行号对互相心仪的列号发起配对请求
    for (int i = 0; i < n; i++) {
        // 记录增广路访问过的列号
        int vis[MAX_SIZE] = {FALSE};

        // 如果当前行号 i 可以找到匹配的列号，则 smallerCount + 1
        if (dfs(i, kth, match, vis)) {
            smallerCount++;
        }
    }

    // 判断是否满足条件：小于等于 kth 的元素个数是否 >= N - K + 1
    return smallerCount >= (n - k + 1);
}

int main() {
    // 读取输入的 N, M, K
    scanf("%d %d %d", &n, &m, &k);

    int min = 1; // 二分枚举的左边界
    int max = INT_MIN; // 二分枚举的右边界，初始为整型最小值

    // 读取矩阵，并找到矩阵中的最大值
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &matrix[i][j]);
            max = (int) fmax(max, matrix[i][j]); // 更新最大值
        }
    }

    // 二分枚举第 K 大的最小取值
    while (min <= max) {
        // mid 是被枚举出来的 N 个数中的第 K 大的最小取值
        int mid = (min + max) >> 1; // 取中间值，相当于 (min + max) / 2

        // 检查 mid 是否可以作为 N 个数中第 K 大的值
        if (check(mid)) {
            // 如果满足条件，尝试更小的值
            max = mid - 1;
        } else {
            // 如果不满足条件，尝试更大的值
            min = mid + 1;
        }
    }

    // 输出结果
    printf("%d\n", min);

    return 0;
}

C++代码

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 150;

int n, m, k;
vector<vector<int>> matrix(MAX_SIZE, vector<int>(MAX_SIZE));

// DFS 实现二分图匹配
bool dfs(int i, int kth, vector<int>& match, vector<bool>& vis) {
    // 行号 i 发起了配对请求
    // 遍历每一个列号 j
    for (int j = 0; j < m; j++) {
        // 如果列号 j 未被访问过，并且矩阵中 matrix[i][j] <= kth
        if (!vis[j] && matrix[i][j] <= kth) {
            vis[j] = true; // 标记列号 j 为已访问

            // 如果列号 j 未配对，或者已配对但可以找到其他行号重新配对
            if (match[j] == -1 || dfs(match[j], kth, match, vis)) {
                // 则当前行号 i 和列号 j 可以配对
                match[j] = i;
                return true;
            }
        }
    }

    // 如果找不到匹配的列号，返回 false
    return false;
}

// 检查函数：判断当前枚举的 kth 是否满足条件
bool check(int kth) {
    // 利用二分图最大匹配来求解，小于等于 kth 的元素个数（即二分图最大匹配）
    int smallerCount = 0;

    // 记录每个列号的匹配成功的行号
    vector<int> match(m, -1); // 初始时每个列号都处于未配对状态

    // 遍历行号，每个行号对互相心仪的列号发起配对请求
    for (int i = 0; i < n; i++) {
        // 记录增广路访问过的列号
        vector<bool> vis(m, false);

        // 如果当前行号 i 可以找到匹配的列号，则 smallerCount + 1
        if (dfs(i, kth, match, vis)) {
            smallerCount++;
        }
    }

    // 判断是否满足条件：小于等于 kth 的元素个数是否 >= N - K + 1
    return smallerCount >= (n - k + 1);
}

int main() {
    // 读取输入的 N, M, K
    cin >> n >> m >> k;

    int minVal = 1; // 二分枚举的左边界
    int maxVal = INT_MIN; // 二分枚举的右边界，初始为整型最小值

    // 读取矩阵，并找到矩阵中的最大值
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
            maxVal = max(maxVal, matrix[i][j]); // 更新最大值
        }
    }

    // 二分枚举第 K 大的最小取值
    while (minVal <= maxVal) {
        // mid 是被枚举出来的 N 个数中的第 K 大的最小取值
        int mid = (minVal + maxVal) >> 1; // 取中间值，相当于 (minVal + maxVal) / 2

        // 检查 mid 是否可以作为 N 个数中第 K 大的值
        if (check(mid)) {
            // 如果满足条件，尝试更小的值
            maxVal = mid - 1;
        } else {
            // 如果不满足条件，尝试更大的值
            minVal = mid + 1;
        }
    }

    // 输出结果
    cout << minVal << endl;

    return 0;
}

代码逻辑详解

1. 输入处理

• 读取输入的 ( N )、( M )、( K )。
• 读取矩阵，并找到矩阵中的最大值 maxVal，作为二分枚举的右边界。

2. 二分枚举

• 初始化二分枚举的左右边界：
  • minVal = 1：最小值从 1 开始。
  • maxVal：矩阵中的最大值。
• 通过二分法枚举可能的第 ( K ) 大的最小值 mid。
• 调用 check(mid) 检查当前 mid 是否满足条件。

3. 检查函数 check(kth)

• 目标：检查是否存在至少 ( N - K + 1 ) 个小于等于 kth 的元素，并且这些元素不在同一行或同一列。
• 实现方式：
  • 使用二分图最大匹配算法。
  • 遍历每一行，尝试匹配一个列号。
  • 如果匹配成功，则 smallerCount + 1。
  • 最终判断 smallerCount 是否大于等于 ( N - K + 1 )。

4. DFS 实现二分图匹配

• 目标：为当前行号 i 找到一个匹配的列号 j。
• 实现方式：
  • 遍历所有列号 j。
  • 如果列号 j 未被访问过，并且矩阵中 matrix[i][j] <= kth，则尝试匹配。
  • 如果列号 j 未配对，或者已配对但可以找到其他行号重新配对，则匹配成功。
  • 返回匹配结果。

5. 输出结果

• 当二分枚举结束时，minVal 即为满足条件的最小值。

关键点总结

1. 二分枚举：通过二分法高效枚举可能的第 ( K ) 大的最小值。
2. 二分图匹配：将问题转化为二分图的最大匹配问题，确保选出的数不在同一行或同一列。
3. DFS 实现匹配：通过 DFS 实现二分图的匹配过程，确保匹配的列号满足条件。

通过以上注释和讲解，你应该能够理解代码的每一部分逻辑和实现方式。如果还有疑问，欢迎随时提出！

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

1. 机试是进入技术面的第一关：
   华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。

2. 技术面试需要手撕代码：
   技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

3. 入职后的可信考试：
   入职华为后，还需要通过“可信考试”。可信考试分为三个等级：

   • 入门级：主要考察基础算法与编程能力。
   • 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
   • 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

1. 关注历年真题：

   • 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
   • 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。

2. 适应新题目：

   • E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
   • 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。

3. 掌握常见算法：
   华为OD考试通常涉及以下算法和数据结构：

   • 排序算法（快速排序、归并排序等）
   • 动态规划（背包问题、最长公共子序列等）
   • 贪心算法
   • 栈、队列、链表的操作
   • 图论（最短路径、最小生成树等）
   • 滑动窗口、双指针算法

4. 保持编程规范：

   • 注重代码的可读性和注释的清晰度。
   • 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

1. 官方参考：

   • 华为招聘官网或相关的招聘平台会有一些参考信息。
   • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。

2. 加入刷题社区：

   • 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
   • 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。

3. 寻找系统性的教程：

   • 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
   • 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

1. 本地编写代码

   • 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。

2. 调整心态，保持冷静

   • 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。

3. 输入输出完整性

   • 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。

4. 快捷键使用

   • 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
   • 避免使用 Ctrl+S，以免触发浏览器的保存功能。

5. 浏览器要求

   • 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。

6. 交卷相关

   • 答题前，务必仔细查看题目示例，避免遗漏要求。
   • 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
   • 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。

7. 时间和分数安排

   • 总时间：150 分钟；总分：400 分。
   • 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。

8. 考试环境准备

   • 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
   • 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。

9. 技术问题处理

   • 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
   • 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！