leetcode

leetcode 搜索二维矩阵 II python 四分法

2019-03-22  本文已影响0人  DaydayHoliday

利用矩阵左上角元素总是最小,右下角总是最大的特性,将矩阵分成四部分,分别递归。
请各位大佬多多提意见。

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        row_num=len(matrix)
        
        if row_num ==0:
            return False
        
        col_num=len(matrix[0])
        if col_num ==0:
            return False
        
        if matrix[0][0] == target:
            return True
        if matrix[-1][-1] == target:
            return True
        if matrix[0][0] > target:
            return False
        if matrix[-1][-1] < target:
            return False
        
        mid_row=int(row_num/2+0.51)
        mid_col=int(col_num/2+0.51)
        
        firstMatrix=[]
        
        for r_ind in range(mid_row):
            firstMatrix.append(matrix[r_ind][0:mid_col])
        
        if self.searchMatrix(firstMatrix,target) == True:
            return True
        
        secondMatrix=[]
        
        for r_ind in range(mid_row):
            secondMatrix.append(matrix[r_ind][mid_col:])
        
        if self.searchMatrix(secondMatrix,target) == True:
            return True
        
        thirdMatrix=[]
        
        for r_ind in range(mid_row,row_num):
            thirdMatrix.append(matrix[r_ind][0:mid_col])
        
        if self.searchMatrix(thirdMatrix,target) == True:
            return True

        fourthMatrix=[]
        
        for r_ind in range(mid_row,row_num):
            fourthMatrix.append(matrix[r_ind][mid_col:])
        
        if self.searchMatrix(fourthMatrix,target) == True:
            return True
                
        return False
上一篇下一篇

猜你喜欢

热点阅读