解題報(bào)告 ? ?- 搜索二維矩陣

LeetCode 搜索二維矩陣

@TOC

題目描述

?編寫一個(gè)高效的算法來判斷 m x n 矩陣中，是否存在一個(gè)目標(biāo)值。該矩陣具有如下特性：

• 每行中的整數(shù)從左到右按升序排列。

• 每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)。

示例：

1輸入：matrix?=?[[1,3,5,7],[10,11,16,20],[23,30,34,60]],?target?=?3?輸出：true


提示：

1m?==?matrix.length
2n?==?matrix[i].length
31?<=?m,?n?<=?100
4-104?<=?matrix[i][j],?target?<=?104


一、解題關(guān)鍵詞

1二維矩陣
2有序


二、解題報(bào)告

1.思路分析

1. 每行有順序，每列有順序

2. 二分 left right mid ，需要找到是否為邊界

3. 因?yàn)閿?shù)據(jù)行 列 都有序 ，先找列 再找行數(shù)據(jù)

4. 不能從中間找（二維數(shù)組，信息過多），要從下往上 或者從上往下找行數(shù)據(jù)

5. 確定行數(shù)據(jù)之后，以此為起點(diǎn) 找列數(shù)據(jù)

2.時(shí)間復(fù)雜度

3.代碼示例

1class?Solution?{
2????//有順序?二分
3????public?boolean?searchMatrix(int[][]?matrix,?int?target)?{
4????????int?rowLen?=?matrix.length?-?1,?colLen?=?0;
5????????while?(rowLen?>=?0?&&?colLen?<?matrix[0].length)?{
6????????????int?num?=?matrix[rowLen][colLen];
7????????????if?(num?==?target)?{
8????????????????return?true;
9????????????}?else?if?(num?>?target){
10????????????????rowLen?--;
11????????????}else{
12????????????????colLen?++;
13????????????}
14????????}
15????????return?false;
16????}
17}


4.知識(shí)點(diǎn)

1