Question

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

English Version

题目描述

给你一个 m x n 的矩阵 mat，其中每一行的元素均符合 严格递增 。请返回 _所有行中的 最小公共元素 _。

如果矩阵中没有这样的公共元素，就请返回 -1。

 

示例 1：

输入：mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
输出：5

示例 2:

输入：mat = [[1,2,3],[2,3,4],[2,3,5]]
输出： 2

 

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 500
• 1 <= mat[i][j] <= 104
• mat[i] 已按严格递增顺序排列。

解法

方法一：计数

我们用一个长度为 $10001$ 的数组 $cnt$ 统计每个数出现的次数。顺序遍历矩阵中的每个数，将其出现次数加一。当某个数的出现次数等于矩阵的行数时，说明该数在每一行都出现过，即为最小公共元素，返回该数即可。

若遍历结束后没有找到最小公共元素，则返回 $-1$。

时间复杂度 $O(m \times n)$，空间复杂度 $O(10^4)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

class Solution:
  def smallestCommonElement(self, mat: List[List[int]]) -> int:
    cnt = Counter()
    for row in mat:
      for x in row:
        cnt[x] += 1
        if cnt[x] == len(mat):
          return x
    return -1

class Solution {
  public int smallestCommonElement(int[][] mat) {
    int[] cnt = new int[10001];
    for (var row : mat) {
      for (int x : row) {
        if (++cnt[x] == mat.length) {
          return x;
        }
      }
    }
    return -1;
  }
}

class Solution {
public:
  int smallestCommonElement(vector<vector<int>>& mat) {
    int cnt[10001]{};
    for (auto& row : mat) {
      for (int x : row) {
        if (++cnt[x] == mat.size()) {
          return x;
        }
      }
    }
    return -1;
  }
};

func smallestCommonElement(mat [][]int) int {
  cnt := [10001]int{}
  for _, row := range mat {
    for _, x := range row {
      cnt[x]++
      if cnt[x] == len(mat) {
        return x
      }
    }
  }
  return -1
}

function smallestCommonElement(mat: number[][]): number {
  const cnt: number[] = new Array(10001).fill(0);
  for (const row of mat) {
    for (const x of row) {
      if (++cnt[x] == mat.length) {
        return x;
      }
    }
  }
  return -1;
}