Sword_Offer 二维数组中的查找[4]

Sword_Offer 二维数组中的查找[4]

0x00 题目描述

题目：在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数

1	2	8	9
2	4	9	12
4	7	10	13
6	8	11	15

0x01 解题思路

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# Author LQ6H

class Solution:
    def Find(self,matrix,number):
        """
        :param matrix: List[List[int]]
        :param number: int
        :return: bool
        """
        if not matrix:
            return False

        row=len(matrix)
        col=len(matrix[0])

        found=False

        i=0
        j=col-1

        while 0<=i<row and 0<=j<col:
            if matrix[i][j]==number:
                found=True
                break
            elif matrix[i][j]>number:
                j-=1
            else:
                i+=1

        return found

0x02 性能分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)