leetcode1380#easy,模拟

题目要求:给出一个矩阵,列出这个矩阵里所有行内最小列内最大的数

最直接 的思路就是 直接比
先找到行内最小,然后遍历它所在的列,满足要求就加入结果集
这种情况下复杂度是O((m+n)*m),完全可以解决。
代码量和时间空间的复杂度上都应该是最优的解法
具体可以参考bloodborne给出的解法

但我当时没估复杂度就觉得会存在多次的比较。。。于是这样做了:
首先找到行内最小,然后标记:他所在的列是x
开一个map存起来:第x列的所在行最小的数字是y
然后遍历map:x列最大的是不是y
这种情况下,复杂度<O(mn+min(m,n)m),在最坏最坏的情况下,与上述的直接的思路相当。
省下来的是因为map的规模<=min(m,n) 每一列都只被比较了一次。
(btw,max和min在go里是给float64的,int没有)
(虽然go的语法真的和c很像很像,但go不允许?:;这种选择判断 需要老老实实if else)
正在习惯go的赋值:var

func luckyNumbers (matrix [][]int) []int {
    m:=len(matrix)
    res:=[]int{}
    addr:=make(map[int]int)
    for i:=0;i<m;i++{
        x:=matrix[i][0]
        var index int=0
        for j,val:=range matrix[i]{
            if val<x{
                index=j
                x=val
            }
        }//m行 最小的是x,位置在index
        if _,ok:=addr[index];ok&&x<addr[index]{
        }else{
            addr[index]=x
            //fmt.Print(index,"is",x," ")
        }
    }
    for x,val:=range addr{
        var i int;
        for i=0;i<m;i++{
            if matrix[i][x]>val{
                break
            }
        }
        if i==m{
            res=append(res,val)
        }
    }
    return res
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容