---

1198. 找出所有行中最小公共元素

• 标签：数组、哈希表、二分查找、计数、矩阵
• 难度：中等

题目链接

• 1198. 找出所有行中最小公共元素 - 力扣

题目大意

描述：给你一个 $m \times n$ 的矩阵 $mat$，每一行中的数字都是严格递增（从小到大，没有重复）的。

要求：找出所有行中都出现的那个最小公共元素。如果没有这样的元素，返回 $-1$。

说明：

• $m == mat.length$。
• $n == mat[i].length$。
• $1 \le m, n \le 500$。
• $1 \le mat[i][j] \le 10^{4}$。
• $mat[i]$ 已按严格递增顺序排列。

示例：

输入：mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
输出：5
解释：数字 5 在每一行都出现了，而且没有比它更小的公共数字了。

解题思路

思路 1：哈希表计数

这道题最简单的思路就是：拿一个计数器（哈希表，可以想象成一个带计票功能的登记本），遍历整个矩阵，每个数字每出现一次就记一票。最后看哪些数字的票数等于总行数 $m$（说明每一行都有它），从中选出最小的那个。

为什么用第一行来查找？
因为所有行都是递增的，第一行也是递增的。我们只要遍历第一行的数字，检查它是否在所有行都出现了，找到的第一个就是最小的。

步骤拆解：

1. 用哈希表统计每个数字在整个矩阵中出现的次数。
2. 遍历第一行的数字（因为是递增的，最小的数字排在最前面）：
   • 如果某个数字出现的次数等于总行数 $m$，说明它在每一行都出现了，直接返回它。
3. 如果第一行都遍历完了还没找到，说明没有公共元素，返回 $-1$。

思路 1：代码

class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        
        # 用一个字典统计每个数字出现的总次数
        count_map = {}
        for i in range(m):
            for j in range(n):
                num = mat[i][j]
                count_map[num] = count_map.get(num, 0) + 1
        
        # 第一行是递增的，遍历第一行找到第一个在所有行都出现的数字
        for num in mat[0]:
            if count_map[num] == m:
                return num
        
        return -1

思路 1：复杂度分析

• 时间复杂度：$O(m \times n)$。用人话说就是：遍历整个矩阵一次就够了。
• 空间复杂度：$O(m \times n)$。最坏情况下矩阵中每个数字都不一样，哈希表就要存全部。