Commit8ac6a67

committed

240 (2) update time complexity

1 parentbbf6b0f commit8ac6a67Copy full SHA for 8ac6a67

File tree

-8

lines changed

-8

lines changed

Lines changed: 9 additions & 8 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,5 +1,5 @@`
`1`	`1`	`/**`
`2`		`- * Time : O(log(mn)) ; Space: O(1)`
	`2`	`+ * Time : O(m + n) ; Space: O(1)`
`3`	`3`	`* @tag : Divide and Conquer; Binary Search`
`4`	`4`	`* @by : Steven Cooks`
`5`	`5`	`* @date: Aug 17, 2015`
`@@ -27,21 +27,22 @@`
`27`	`27`	`/** see test {@link _240_SearchA2DMatrixII.SolutionTest } */`
`28`	`28`	`publicclassSolution {`
`29`	`29`
	`30`	`+// start from top right corner`
`30`	`31`	`publicbooleansearchMatrix(int[][]matrix,inttarget) {`
`31`	`32`	`if (matrix.length ==0 \|\|matrix[0].length ==0) {`
`32`	`33`	`returnfalse;`
`33`	`34`	`}`
`34`	`35`	`introws =matrix.length;`
`35`	`36`	`intcols =matrix[0].length;`
`36`		`-intj =0;`
`37`		`-inti =cols -1;;`
`38`		`-while (j <rows &&i >=0) {`
`39`		`-if (matrix[j][i] ==target) {`
	`37`	`+inti =0;`
	`38`	`+intj =cols -1;`
	`39`	`+while (i <rows &&j >=0) {`
	`40`	`+if (matrix[i][j] ==target) {`
`40`	`41`	`returntrue;`
`41`		`- }elseif (matrix[j][i] <target) {`
`42`		`-j++;`
	`42`	`+ }elseif (matrix[i][j] <target) {`
	`43`	`+i++;`
`43`	`44`	`}else {`
`44`		`-i--;`
	`45`	`+j--;`
`45`	`46`	`}`
`46`	`47`	`}`
`47`	`48`	`returnfalse;`

Comments

(0)