74. Search a 2D Matrix

讲真这题ac太快，我觉得有点简单，所以别人的方法应该会比我的好。不管怎样，先记下我的代码：

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

突然就想起来剑指offer上的一道题目，按照那一题的做法，代码如下：

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

事实证明这道题确实有特别多的解法，因为矩阵的特性可以将其看作是一个一维数组，因此用一维数组的办法来做这一题，代码如下：

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        #一维数组的办法
        res = []
        for i in matrix:
            res += i
        start = 0
        end = len(res) - 1
        while start <= end:
            mid = (start + end) / 2
            if res[mid] == target:
                return True
            elif res[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        return False

其实不用特意构造一个一维数组，可以直接通过下标来表示，上面的方法比较笨，下面是改良版本的，代码如下：

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        #一维数组的办法
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        if n == 0:
            return False
        start = 0
        end = m * n - 1
        while start <= end :
            mid = (start + end) / 2
            r = mid / n
            c = mid % n
            if matrix[r][c] == target:
                return True
            elif matrix[r][c] < target:
                start = mid + 1
            else:
                end = mid - 1
        return False

两次二分查找的办法，先按照行进行查找，不过这里情况要复杂一些，因为还要考虑到，虽然大于行首的数字但还是有可能在这一行，因此判断不在这一行的办法就是头和尾都小于target或者头部大于target，因此如果头部小于target 尾部大于target 很有可能就在这一行就需要break，当然判断是否等于mid,也是要头部或者尾部的。代码如下：

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        #一维数组的办法
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        if n == 0:
            return False
        start = 0
        end = m - 1
        mid = 0
        while start <= end:
            mid = (start + end) / 2
            if matrix[mid][0] == target or matrix[mid][n-1] == target:
                return True
            elif matrix[mid][0] < target and matrix[mid][n-1] > target:
                break
            elif matrix[mid][0] > target:
                end = mid - 1
            else:
                start = mid + 1
        left = 0
        right = n - 1
        while left <= right:
            mid2 = (left + right) / 2
            if matrix[mid][mid2] == target:
                return True
            elif matrix[mid][mid2] < target:
                left = mid2 + 1
            else:
                right = mid2 - 1
        return False

这么看来上述这么多做法，虽然思想就几种，但是同一种思想做法也有好坏之分，总之，最上面的AC太快的可谓是暴力解法了。