您好,登錄后才能下訂單哦!
題目描述
在一個二維數(shù)組中(每個一維數(shù)組的長度相同),每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數(shù),輸入這樣的一個二維數(shù)組和一個整數(shù),判斷數(shù)組中是否含有該整數(shù)。
題目分析:
由于所給的二維數(shù)組在一定程度上是有序的,即每一行、每一列都是有序的,但是行與行之間不一定是有序的。如:1 2 3
2 3 4
3 4 5第二行的2和第一行的3并不是有序的。
因此,如果從左上角坐標(biāo)為(0, 0)開始遍歷這個二維數(shù)組的話,如果當(dāng)前的數(shù)字小于要查找的目標(biāo)數(shù)字,那么要查找的數(shù)字就可能出現(xiàn)在當(dāng)前數(shù)字的右邊或左邊,導(dǎo)致問題變復(fù)雜。
相反,如果我們換個思路,從數(shù)組的左下角或者右上角開始遍歷,以左下角為例,如果當(dāng)前的數(shù)字小于目標(biāo)數(shù)字,那么就往右查找,反之往上查找。這樣每次判斷完之后只有一個方向需要遍歷,問題就變得不復(fù)雜了。
# -*- coding:utf-8 -*-
class Solution:
# array 二維列表
def Find(self, target, array):
m, n = len(array), len(array[0])
i, j = m - 1, 0 # 從左下角開始
while i >= 0 and j < n: # 因為我們只會往右、往上走,所以i只會減,j只會加,因此只需要保證i,j不越界即可
if array[i][j] == target:
return True
if array[i][j] > target: # 目標(biāo)數(shù)字比當(dāng)前數(shù)字小,往上
i -= 1
else: # 目標(biāo)數(shù)字比當(dāng)前數(shù)字大,往右
j += 1
return False
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。