溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶(hù)服務(wù)條款》

Lintcode28 Search a 2D Matrix solution 題解

發(fā)布時(shí)間：2020-08-13 07:35:26 來(lái)源：網(wǎng)絡(luò) 閱讀：483 作者：coderer 欄目：軟件技術(shù)

【題目描述】

Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:Integers in each row are sorted from left to right.The first integer of each row is greater than the last integer of the previous row.

寫(xiě)出一個(gè)高效的算法來(lái)搜索 m × n矩陣中的值。

這個(gè)矩陣具有以下特性：每行中的整數(shù)從左到右是排序的。每行的第一個(gè)數(shù)大于上一行的最后一個(gè)整數(shù)。

【題目鏈接】

http://www.lintcode.com/en/problem/search-a-2d-matrix/

【題目解析】

對(duì)于這個(gè)給定的矩陣，我們?nèi)绻胋rute force解法，用兩個(gè)嵌套循環(huán)，O(n2)便可以得到答案.但是我們需要注意的是這道題已經(jīng)給定了這個(gè)矩陣的兩個(gè)特性，這兩個(gè)特性對(duì)于提

高我們算法的時(shí)間復(fù)雜度有很大幫助，首先我們給出一個(gè)O(n)的解法，也就是說(shuō)我們可以固定住右上角的元素，根據(jù)遞增或者遞減的規(guī)律，我們可以判斷這個(gè)給定的數(shù)值是否存在于這個(gè)矩陣當(dāng)中.

【參考答案】

http://www.jiuzhang.com/solutions/search-a-2d-matrix/


向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手