Commitc4d9e4c

applewjg

committed

Searcha2DMatrix

Change-Id: I607d6421b973f90061d0b13a1ee45739064b8283

1 parent4728759 commitc4d9e4cCopy full SHA for c4d9e4c

File tree

+39

-0

lines changed

+39

-0

lines changed

Lines changed: 39 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,39 @@`
	`1`	`+/*`
	`2`	`+ Author: Andy, nkuwjg@gmail.com`
	`3`	`+ Date: Jan 16, 2015`
	`4`	`+ Problem: Search a 2D Matrix`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: https://oj.leetcode.com/problems/search-a-2d-matrix/`
	`7`	`+ Notes:`
	`8`	`+ Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:`
	`9`	`+`
	`10`	`+ Integers in each row are sorted from left to right.`
	`11`	`+ The first integer of each row is greater than the last integer of the previous row.`
	`12`	`+ For example,`
	`13`	`+`
	`14`	`+ Consider the following matrix:`
	`15`	`+`
	`16`	`+ [`
	`17`	`+ [1, 3, 5, 7],`
	`18`	`+ [10, 11, 16, 20],`
	`19`	`+ [23, 30, 34, 50]`
	`20`	`+ ]`
	`21`	`+ Given target = 3, return true.`
	`22`	`+`
	`23`	`+ Solution: Binary-search.`
	`24`	`+ */`
	`25`	`+publicclassSolution {`
	`26`	`+publicbooleansearchMatrix(int[][]matrix,inttarget) {`
	`27`	`+if (matrix.length ==0 \|\|matrix[0].length ==0)returnfalse;`
	`28`	`+intN =matrix.length,M =matrix[0].length;`
	`29`	`+intleft =0,right =M *N -1;`
	`30`	`+while (left <=right) {`
	`31`	`+intmid =left + (right -left) /2;`
	`32`	`+introw =mid /M,col =mid %M;`
	`33`	`+if (matrix[row][col] ==target)returntrue;`
	`34`	`+if (matrix[row][col] <target)left =mid +1;`
	`35`	`+elseright =mid -1;`
	`36`	`+ }`
	`37`	`+returnfalse;`
	`38`	`+ }`
	`39`	`+}`

Comments

(0)