每日一道算法題--二維數(shù)組中的查找--python

番茄西紅柿發(fā)布于2019-05-23 16:08 / 651人閱讀

摘要：題目描述代碼思路思路一按行執(zhí)行二分查找，只要該行的第一個元素小于目標，就對該行二分查找。思路二從數(shù)組的左下角開始查找，如果當前值小于目標，就向右，即如果當前值大于目標，就向上，即。

【題目描述】

【代碼思路】 思路一：按行執(zhí)行二分查找，只要該行的第一個元素小于目標，就對該行二分查找。思路二：從數(shù)組的左下角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]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 targetelif target>array[i][j]:
                j += 1
            else:
                return True
        return False

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/7138.html

相關(guān)文章

每日一道算法題--二維數(shù)組中的查找--python

摘要：題目描述代碼思路思路一按行執(zhí)行二分查找，只要該行的第一個元素小于目標，就對該行二分查找。思路二從數(shù)組的左下角開始查找，如果當前值小于目標，就向右，即如果當前值大于目標，就向上，即。【題目描述】 showImg(https://user-gold-cdn.xitu.io/2019/5/22/16addf094e0320ca); 【代碼思路】思路一：按行執(zhí)行二分查找，只要該行的第一個元素小于目...

luck 2019-05-23 11:56 評論0 收藏0
每日一道算法題--leetcode 746--使用最小花費爬樓梯--python

摘要：代碼思路最簡單的一維動態(tài)規(guī)劃問題，自底向上。上代碼看效果，時間復雜度線性級別這里有一個動態(tài)規(guī)劃系列題目整理，供大家參考【題目描述】 showImg(https://user-gold-cdn.xitu.io/2019/5/27/16af88f6f38f5da3); ?。☆}干里的示例1需要仔細看一下哦，要到達頂層，即20那一層，可以跳過20這一層達到更高一層，也因此我們給cost數(shù)組最后加一個...

Euphoria 2019-05-27 17:41 評論0 收藏0
每日一道算法題 - LongestWord(easy-1)

摘要：規(guī)則使用語言，讓函數(shù)獲取傳遞的參數(shù)并返回字符串中的最大單詞。忽略字符串中標點符號并假設(shè)不會為空。測試用例思路通過過濾字符串，并把字符串根據(jù)空格符轉(zhuǎn)換成字符串數(shù)組通過循環(huán)把獲取字符串數(shù)組中的長度最長的字符串雖然都是很簡單的算法，每個都只需5分鐘左右，但寫起來總會遇到不同的小問題，希望大家能跟我一起每天進步一點點。更多的小算法練習，可以查看我的文章。規(guī)則 Using the JavaS...

plokmju88 2019-08-22 18:35 評論0 收藏0
每日一道算法題 - 反轉(zhuǎn)字符串(easy-3)

摘要：規(guī)則使用語言，讓函數(shù)獲取傳遞的參數(shù)，并以相反的順序返回字符串。測試用例思路方法通過把字符串轉(zhuǎn)換成數(shù)組，并使用數(shù)組的反轉(zhuǎn)數(shù)組，然后使用重新拼接成字符串方法向后循環(huán)字符串或字符數(shù)組以生成新字符串雖然都是很簡單的算法，每個都只需5分鐘左右，但寫起來總會遇到不同的小問題，希望大家能跟我一起每天進步一點點。更多的小算法練習，可以查看我的文章。規(guī)則 Using the JavaScript l...

xfee 2019-08-22 18:36 評論0 收藏0
每日一道算法題

摘要：遇到的坑剛拿到這道題就直接做了這樣的判斷，可是萬一是這個判斷就是錯誤的了。思路二上述算法遍歷了兩次鏈表，還額外申請了一個數(shù)組空間，效率不高，不如直接就地反轉(zhuǎn)鏈表，更改每個節(jié)點自身的指針。 2018.10.14 來源：劍指offer 題目：反轉(zhuǎn)鏈表輸入一個鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭。思路一：把所有鏈表內(nèi)容都輸入到一個數(shù)組，再次遍歷鏈表，得到數(shù)組反轉(zhuǎn)后的值，最后輸出原來的head...

The question 2019-08-23 12:21 評論0 收藏0