Commit58f4bfa

committed

add a solution for 378

1 parent2f77c80 commit58f4bfaCopy full SHA for 58f4bfa

File tree

+33

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _378.java
- test/java/com/fishercoder
  - _378Test.java

+33

-0

lines changed

Lines changed: 21 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -3,6 +3,7 @@`
`3`	`3`	`importjava.util.ArrayList;`
`4`	`4`	`importjava.util.Collections;`
`5`	`5`	`importjava.util.List;`
	`6`	`+importjava.util.PriorityQueue;`
`6`	`7`
`7`	`8`	`publicclass_378 {`
`8`	`9`	`publicstaticclassSolution1 {`
`@@ -52,4 +53,24 @@ public int kthSmallest(int[][] matrix, int k) {`
`52`	`53`	`returnlo;`
`53`	`54`	`}`
`54`	`55`	`}`
	`56`	`+`
	`57`	`+publicstaticclassSolution3 {`
	`58`	`+/**`
	`59`	`+ * use heap data structure`
	`60`	`+ */`
	`61`	`+publicintkthSmallest(int[][]matrix,intk) {`
	`62`	`+PriorityQueue<int[]>heap =newPriorityQueue<>((a,b) ->a[0] -b[0]);`
	`63`	`+for (inti =0;i <matrix.length;i++) {`
	`64`	`+//we store value, rowIndex, colIndex as an array into this heap`
	`65`	`+heap.offer(newint[]{matrix[i][0],i,0});`
	`66`	`+ }`
	`67`	`+while (k-- >1) {`
	`68`	`+int[]min =heap.poll();`
	`69`	`+if (min[2] +1 <matrix[min[1]].length) {`
	`70`	`+heap.offer(newint[]{matrix[min[1]][min[2] +1],min[1],min[2] +1});`
	`71`	`+ }`
	`72`	`+ }`
	`73`	`+returnheap.poll()[0];`
	`74`	`+ }`
	`75`	`+ }`
`55`	`76`	`}`

Lines changed: 12 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -10,12 +10,14 @@`
`10`	`10`	`publicclass_378Test {`
`11`	`11`	`privatestatic_378.Solution1solution1;`
`12`	`12`	`privatestatic_378.Solution2solution2;`
	`13`	`+privatestatic_378.Solution3solution3;`
`13`	`14`	`privatestaticint[][]matrix;`
`14`	`15`
`15`	`16`	`@BeforeClass`
`16`	`17`	`publicstaticvoidsetup() {`
`17`	`18`	`solution1 =new_378.Solution1();`
`18`	`19`	`solution2 =new_378.Solution2();`
	`20`	`+solution3 =new_378.Solution3();`
`19`	`21`	`}`
`20`	`22`
`21`	`23`	`@Test`
`@@ -25,13 +27,23 @@ public void test1() {`
`25`	`27`	`};`
`26`	`28`	`assertEquals(-5,solution1.kthSmallest(matrix,1));`
`27`	`29`	`assertEquals(-5,solution2.kthSmallest(matrix,1));`
	`30`	`+assertEquals(-5,solution3.kthSmallest(matrix,1));`
`28`	`31`	`}`
`29`	`32`
`30`	`33`	`@Test`
`31`	`34`	`publicvoidtest2() {`
`32`	`35`	`matrix =CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,2],[1,3]");`
`33`	`36`	`assertEquals(1,solution1.kthSmallest(matrix,2));`
`34`	`37`	`assertEquals(1,solution2.kthSmallest(matrix,2));`
	`38`	`+assertEquals(1,solution3.kthSmallest(matrix,2));`
	`39`	`+ }`
	`40`	`+`
	`41`	`+@Test`
	`42`	`+publicvoidtest3() {`
	`43`	`+matrix =CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,5,9],[10,11,13],[12,13,15]");`
	`44`	`+assertEquals(13,solution1.kthSmallest(matrix,8));`
	`45`	`+assertEquals(13,solution2.kthSmallest(matrix,8));`
	`46`	`+assertEquals(13,solution3.kthSmallest(matrix,8));`
`35`	`47`	`}`
`36`	`48`
`37`	`49`	`}`

Comments

(0)