云博(司云中)
Leetcode --剑指Offer 04.二维数组的查找

阅读量:(23) 您现在所在的位置: 首页 百宝箱 Leetcode Leetcode --剑指Offer 04.二维数组的查找 作者:SmartCloud(云中)
简介:Leetcode --剑指Offer 04.二维数组的查找

解题思路

此题苏大考研初试中曾经考过一次.

思路:

将target只与右上角的元素进行比较:

1.如果target < 右上角元素值,则表明右上角元素所在的列中肯定是没有该元素的,因此比较前一列.

2.如果target > 右上角元素值,则表明右上角元素所在的行中肯定是没有该元素的,因此比较下一行.

3.如果target == 右上角元素值,则表明matrix中存在该target,返回True

注:对于边界情况应该要仔细考虑,避免数组越界!


代码

class Solution(object):
    def findNumberIn2DArray(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix:
            return False

        # 从右上角删除元素,如果小于右上角,则删除第一列,大于右上角,则删除第一行
        row_total = len([row for row in matrix])
        col_total = len([col for col in matrix[0]])
        row, col = 0, -1

        while row < row_total and abs(col) - 1 < col_total:
            print(col)
            right_top = matrix[row][col]
            if target < right_top:
                if abs(col) < col_total:
                    right_top = matrix[row][col - 1]
                col -= 1
            elif target > right_top:
                if row + 1 < row_total:
                    right_top = matrix[row + 1][col]
                row += 1
            else:
                return True
        return False

时间复杂度为: O(n+m)

空间复杂度为: O(1)

点赞一波

0

    欢迎您游客

 小云标签


 网站统计:


笔记数: 总点赞量:

总访问量:   分类数目:

服务器:阿里云服务器