【LintCode 简单】28. 搜索二维矩阵

忘是亡心i 2022-11-25 13:14 86阅读 0赞

1.问题描述：

写出一个高效的算法来搜索 *m* × *n*矩阵中的值。

这个矩阵具有以下特性：

*  每行中的整数从左到右是排序的。
 *  每行的第一个数大于上一行的最后一个整数。

2.样例：

> 样例  1:  
>     输入: \[\[5\]\],2  
>     输出: false  
>       
>     样例解释:   
>   没有包含，返回false。
> 
> 样例 2:  
>     输入:    
> \[  
>   \[1, 3, 5, 7\],  
>   \[10, 11, 16, 20\],  
>   \[23, 30, 34, 50\]  
> \],3  
>     输出: true  
>       
>     样例解释:   
>     包含则返回true。

3.代码：

class Solution:
        """
        @param matrix: matrix, a list of lists of integers
        @param target: An integer
        @return: a boolean, indicate whether matrix contains target
        """
    
        def searchMatrix(self, matrix, target):
            # write your code here
            m = len(matrix)
            n = len(matrix[0])
            mm = 0
            if target < matrix[0][0]:
                return False
            for i in range(m):
                print(i)
                if target >= matrix[i][0] and target <= matrix[i][n - 1]:
                    mm = i
                    break
            for j in range(n):
                if target == matrix[mm][j]:
                    return True
            return False

注意：这里所给的matrix实际是一个二维的list，没有shape属性，需要通过len()方法来获取它的m和n。另外，这里时间复杂度是O(m)+O(n)，如果想要实现O(log(m)+log(n))的话，需要使用二分搜索方法。

发表评论取消回复

表情：

评论列表（有 0 条评论，86人围观）

还没有评论，来说两句吧...

相关阅读

相关 74. 搜索二维矩阵

编写一个高效的算法来判断 `m x n` 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个

不念不忘少年蓝@/ 2023年10月04日 09:12/ 0 赞/ 15 阅读

相关【LintCode 简单】28. 搜索二维矩阵

1.问题描述：写出一个高效的算法来搜索 m × n矩阵中的值。这个矩阵具有以下特性：每行中的整数从左到右是排序的。每行的第一个数大于上一行的最后一个整

忘是亡心i/ 2022年11月25日 13:14/ 0 赞/ 87 阅读

相关 LeetCode74. 搜索二维矩阵

难度：`中等` 题目描述： > 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： > > 每行中的整数从左到右按升序排列。 >

比眉伴天荒/ 2022年11月15日 03:42/ 0 赞/ 174 阅读

相关搜索二维矩阵(二分法)

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。

叁歲伎倆/ 2022年10月25日 15:27/ 0 赞/ 165 阅读

相关 74. 搜索二维矩阵

> 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： > > 每行中的整数从左到右按升序排列。 > 每行的第一个整数大于前一行的最后

偏执的太偏执、/ 2022年10月08日 11:19/ 0 赞/ 178 阅读

相关 1040 搜索二维矩阵

Description 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性： 1. 每行的元素从左到右

傷城~/ 2022年09月12日 03:49/ 0 赞/ 153 阅读

相关 74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。

朱雀/ 2022年08月31日 07:17/ 0 赞/ 171 阅读

相关 LeetCode 240 搜索二维矩阵

题目：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从

短命女/ 2022年03月16日 12:13/ 0 赞/ 248 阅读

相关 LeetCode 74. 搜索二维矩阵

AC1 AC1总是最暴力的 O(n2) class Solution: def searchMatrix(self, matrix, targe

旧城等待，/ 2022年03月14日 12:50/ 0 赞/ 241 阅读

相关 LeetCode----------------------搜索二维矩阵

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。

￡神魔★判官ぃ/ 2021年12月10日 12:37/ 0 赞/ 268 阅读