Medium

题目描述

给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数矩阵 mat。arr 和 mat 都包含范围 [1, m * n] 内的所有整数。

从下标 0 开始遍历 arr 中的每个下标 i，并将 mat 中包含整数 arr[i] 的格子涂色。

请你找出 arr 中在 mat 的某一行或某一列上都被涂色时最小的下标 i。

示例 1：

输入：arr = [1,3,4,2], mat = [[1,4],[2,3]]
输出：2
解释：遍历如上图所示，arr[2] 在矩阵中的第一行和第二列都被涂色。

示例 2：

输入：arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
输出：3
解释：arr[3] 在矩阵中的第二列都被涂色。

提示：

  • m == mat.length
  • n = mat[i].length
  • arr.length == m * n
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • 1 <= arr[i], mat[r][c] <= m * n
  • arr 的所有元素 互不相同
  • mat 的所有元素 互不相同

解题思路

这道题的核心思路是模拟涂色过程并实时跟踪每行每列的涂色进度。

解题思路：

  1. 预处理位置映射：首先遍历矩阵，为每个数值建立位置映射，存储每个数字在矩阵中的行列坐标。

  2. 计数器策略：使用两个计数数组分别记录每行和每列已被涂色的格子数量。

    • rowCount[i]：第 i 行已涂色的格子数
    • colCount[j]：第 j 列已涂色的格子数

  3. 模拟涂色过程：按照数组 arr 的顺序逐个涂色：

    • 根据当前数值找到其在矩阵中的位置 (row, col)
    • 将对应行和列的计数器加一
    • 检查是否某行计数达到列数 n（该行完全涂色）
    • 检查是否某列计数达到行数 m（该列完全涂色）
    • 如果满足条件之一，返回当前索引

  4. 优化点：

    • 使用哈希表进行 O(1) 位置查找
    • 每次涂色后立即检查完成条件，避免不必要的后续操作

这种方法的时间复杂度为 O(m×n)，空间复杂度为 O(m×n)，是最优解法。

代码实现

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        unordered_map<int, pair<int, int>> pos;
        
        // 预处理：建立数值到位置的映射
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                pos[mat[i][j]] = {i, j};
            }
        }
        
        vector<int> rowCount(m, 0), colCount(n, 0);
        
        // 模拟涂色过程
        for (int i = 0; i < arr.size(); i++) {
            auto [row, col] = pos[arr[i]];
            rowCount[row]++;
            colCount[col]++;
            
            // 检查是否有完整的行或列
            if (rowCount[row] == n || colCount[col] == m) {
                return i;
            }
        }
        
        return -1; // 理论上不会到达这里
    }
};

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        pos = {}
        
        # 预处理：建立数值到位置的映射
        for i in range(m):
            for j in range(n):
                pos[mat[i][j]] = (i, j)
        
        row_count = [0] * m
        col_count = [0] * n
        
        # 模拟涂色过程
        for i, num in enumerate(arr):
            row, col = pos[num]
            row_count[row] += 1
            col_count[col] += 1
            
            # 检查是否有完整的行或列
            if row_count[row] == n or col_count[col] == m:
                return i
        
        return -1  # 理论上不会到达这里

public class Solution {
    public int FirstCompleteIndex(int[] arr, int[][] mat) {
        int m = mat.Length, n = mat[0].Length;
        Dictionary<int, (int, int)> pos = new Dictionary<int, (int, int)>();
        
        // 预处理：建立数值到位置的映射
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                pos[mat[i][j]] = (i, j);
            }
        }
        
        int[] rowCount = new int[m];
        int[] colCount = new int[n];
        
        // 模拟涂色过程
        for (int i = 0; i < arr.Length; i++) {
            var (row, col) = pos[arr[i]];
            rowCount[row]++;
            colCount[col]++;
            
            // 检查是否有完整的行或列
            if (rowCount[row] == n || colCount[col] == m) {
                return i;
            }
        }
        
        return -1; // 理论上不会到达这里
    }
}

var firstCompleteIndex = function(arr, mat) {
    const m = mat.length, n = mat[0].length;
    const pos = new Map();
    
    // 预处理：建立数值到位置的映射
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            pos.set(mat[i][j], [i, j]);
        }
    }
    
    const rowCount = new Array(m).fill(0);
    const colCount = new Array(n).fill(0);
    
    // 模拟涂色过程
    for (let i = 0; i < arr.length; i++) {
        const [row, col] = pos.get(arr[i]);
        rowCount[row]++;
        colCount[col]++;
        
        // 检查是否有完整的行或列
        if (rowCount[row]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m×n)预处理矩阵需要 O(m×n)，遍历数组需要 O(m×n)，总体为 O(m×n)
空间复杂度O(m×n)位置映射哈希表需要 O(m×n) 空间，行列计数器需要 O(m+n) 空间

相关题目