LEETCODE 1198. Find Smallest Common Element in All Rows 解题思路分析

题目大意:

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

给你一个矩阵 mat,其中每一行的元素都已经按 递增 顺序排好了。请你帮忙找出在所有这些行中 最小的公共元素。

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

示例1:

Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5

提示:

  • 1 <= mat.length, mat[i].length <= 500
  • 1 <= mat[i][j] <= 10^4
  • mat[i] 已按递增顺序排列。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1198

解题思路分析:

因为要求出所有行的最小公共元素,因此,该元素一定存在于每一行中,也就是说这个公共元素一定是在第一行的某个元素中产生(如果第一行都没有该元素,那肯定不是公共元素)。我们可以使用一个数组来记录第一行的每个元素出现过的次数,如果出现次数等于行数,那么他就是公共元素,在其中找到最小的一个即是本题的解。

实现代码:

public int smallestCommonElement(int[][] mat) {
    // 如果只有一行,首元素即为最小值,直接返回
    if(mat.length==1) return mat[0][0];
    // 记录首行每个元素出现过的次数
    int[] map=new int[10001];
    // 初始化首行元素出现次数均为1
    for(int num : mat[0]){
        map[num]=1;
    }
    // 从第二行开始循环
    for(int i=1;i<mat.length;i++){
        // 循环当前行每个元素
        for(int num : mat[i]){
            // 如果该元素出现次数与行数相同
            // 说明之前每行都出现过该元素
            if(map[num]==i){
                // 如果当前是最后一行
                if(i==mat.length-1){
                    // 返回第一个公共元素(最小)
                    return num;
                }
                // 当前元素个数加一
                map[num]++;
            }
        }
    }
    return -1;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 74.65% of Java online submissions for Find Smallest Common Element in All Rows.

Memory Usage: 63.9 MB, less than 100.00% of Java online submissions for Find Smallest Common Element in All Rows.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1198-find-smallest-common-element-in-all-rows-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。