[Leetcode][python]Search a 2D Matrix/搜索二维矩阵

墨蓝 2022-06-07 10:52 148阅读 0赞

## 题目大意 ##

在一个每行从左到右依次递增，且下一行第一个数字比上一行最后一个数字大的矩阵中，判断目标数字是否存在。

## 解题思路 ##

二分搜索：  
思路1：第一次二分搜索出在哪一行，第二次二分搜索直接确定存在

思路2：其实和思路1还是相通的

把矩阵从左到右、从上到下连起来就是一个递增的数组，可以用二分搜索来查找。现在只要找出数组下标到矩阵的映射关系就可以了：i -> \[i // n\]\[i % n\]，其中i是数组中的下标，n是矩阵的宽。

## 代码 ##

### 思路0 ###

从左下角或者右上角开始查找！经典答案

class Solution(object):
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            i = 0
            j = len(matrix[0]) - 1
            while i < len(matrix) and j >= 0:
                if matrix[i][j] == target: 
                    return True
                elif matrix[i][j] > target: 
                    j -= 1
                else: 
                    i += 1
            return False

### 思路1（易懂） ###

class Solution(object):
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            if not matrix or not len(matrix[0]) :
                return False
            left = 0
            right = len(matrix)-1
            while left <= right:
                mid = (left + right) / 2  # 只保留整数
                # print left, right, matrix[mid][0]
                if matrix[mid][0] > target:
                    right = mid - 1
                elif matrix[mid][0] < target:
                    left = mid + 1
                else:
                    return True
    
            x = left - 1 # 这样出来如果没匹配正好的数，到出循环时就是大于要查找的那个数一位
            print '--', x
            left = 0
            right = len(matrix[0])-1
            while left <= right:
                mid = (left + right) / 2  # 只保留整数
                # print left, right, matrix[x][mid]
                if matrix[x][mid] > target:
                    right = mid - 1
                elif matrix[x][mid] < target:
                    left = mid + 1
                else:
                    return True
            return False

### 思路2 ###

这个过不了牛客网的剑指offer，貌似是由于牛客网的case里允许重复数值，二leetcode是严格升序

class Solution(object):
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            if not matrix or not len(matrix[0]) :
                return False
            m = len(matrix)
            n = len(matrix[0])
            l, h = 0, m * n - 1
            while l <= h:
                mid = l + (h - l) // 2
                # print l, h, mid
                # print matrix[mid // n][mid % n]
                if matrix[mid // n][mid % n] == target:
                    return True
                elif matrix[mid // n][mid % n] < target:
                    l = mid + 1
                else:
                    h = mid - 1
            return False

## 总结 ##

二分搜索的注意：  
编写二分查找的程序时  
如果令 `left <= right，则right = middle - 1;`  
如果令`left < right，则 right = middle;`  
[https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/04.01.md][https_github.com_julycoding_The-Art-Of-Programming-By-July_blob_master_ebook_zh_04.01.md]

[https_github.com_julycoding_The-Art-Of-Programming-By-July_blob_master_ebook_zh_04.01.md]: https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/04.01.md