每日一道算法题--二维数组中的查找--python

栏目: Python · 发布时间: 6年前

内容简介:思路一:按行执行二分查找,只要该行的第一个元素小于目标,就对该行二分查找。 思路二:从数组的左下角array[j][i]开始查找,如果当前值小于目标,就向右,即i+1;如果当前值大于目标,就向上,即j-1。

【题目描述】

每日一道算法题--二维数组中的查找--python
【代码思路】

思路一:按行执行二分查找,只要该行的第一个元素小于目标,就对该行二分查找。 思路二:从数组的左下角array[j][i]开始查找,如果当前值小于目标,就向右,即i+1;如果当前值大于目标,就向上,即j-1。

【源代码】

思路1:时间复杂度0(nlogn)
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if(len(array)==0 or len(array[0])==0):return False
        for i in range(0,len(array)):
            if(array[i][0]>target):
                break
            num=array[i]
            left=0
            right=len(num)-1
            while left<=right:
                mid=int((left+right)/2)
                if(num[mid]>target):
                    right=mid-1
                elif(num[mid]<target):
                    left=mid+1
                else:
                    return True
        return False
                
复制代码
思路2:时间复杂度:O(n)

class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows = len(array) - 1
        cols= len(array[0]) - 1
        i = rows
        j = 0
        while j<=cols and i>=0:
            if target<array[i][j]:
                i -= 1
            elif target>array[i][j]:
                j += 1
            else:
                return True
        return False
复制代码

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Host Your Web Site In The Cloud

Host Your Web Site In The Cloud

Jeff Barr / SitePoint / 2010-9-28 / USD 39.95

Host Your Web Site On The Cloud is the OFFICIAL step-by-step guide to this revolutionary approach to hosting and managing your websites and applications, authored by Amazon's very own Jeffrey Barr. "H......一起来看看 《Host Your Web Site In The Cloud》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试