美文网首页
Leetcode - 74. Search a 2D Matri

Leetcode - 74. Search a 2D Matri

作者: KkevinZz | 来源:发表于2017-04-03 09:30 被阅读0次

    Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

    Integers in each row are sorted from left to right.
    The first integer of each row is greater than the last integer of the previous row.
    For example,

    Consider the following matrix:

    [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
    ]
    Given target = 3, return true.


    Search a 2D Matrix


    解法:
    通过binary search啦!,首先这个matrix其实就是一个拆分开来的sortedlsit,我们先判断是在那个row里面,在对row是用binary search 或者 x in ls的py 的语法

    class Solution(object):
        # def bs(self,ls,key):
        #     h = 0
        #     e = len(ls)-1
        #
        #     while True:
        #         if h == e and ls[h]  != key:
        #             return False
        #         m = h+e/2
        #         if ls[m] > key:
    
    
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            for i in matrix:
                h ,t = i[0],i[-1]
                if h == key or t == key:
                    return True
    
                if h<target and t> target:
                        return target in i
            return False
    
    def bs(self,ls,t):
        s = 0
        e = len(ls)-1
    
        while True:
            print(s,e)
            if e-s == 1:
                return ls[s] == t or ls[e] == t
    
            m = int(((s+e)+0.0)/2)
            if ls[m] == t:
                return True
            if ls[m] > t:
                e = m
            else:
                s = m
        return False
    
    

    相关文章

      网友评论

          本文标题:Leetcode - 74. Search a 2D Matri

          本文链接:https://www.haomeiwen.com/subject/mrvnottx.html