【LEETCODE】74-Search a 2D Matrix [Python]

1834 ワード

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.
タイトル:
有効なアルゴリズムを書いてm x n行列の中である値が存在するかどうかを探します
この行列では、各行が左から右に並んでいます
各行の最初の整数は、前の行の最後の整数よりも大きくなります.
考え方:
検索行rowをロックするには、targetと各行の最初の要素を比較します.
それからrowのあの行で捜索を行って、等しいことに出会ってtrue、小さいことに出会って前進して、前はすべて小さい後の1歩は大きいことに出会って、falseを説明して、1行はすべて比較してまだfalseではありません
方法2:二分検索
http://www.cnblogs.com/zuoyuan/archive/2014/06/05/3770061.html
Python
class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        
        row=0
        m=len(matrix)
        n=len(matrix[0])
        
        if target>=matrix[m-1][0]:<span style="white-space:pre">		</span>#   target            ,        row
            row=m-1
        else:
            for i in range(len(matrix)):
                if target<matrix[i][0]:
                    row=i-1
                    break             
        if row<0:
            return False
            
        j=0<span style="white-space:pre">					</span>#  row       
        while j<n:
            if matrix[row][j]==target:
                return True
            elif matrix[row][j]>target:
                return False
            else:
                j+=1
                
        return False