@@ -23,7 +23,28 @@ public int kthSmallest(int[][] matrix, int k) {
2323 }
2424 }
2525
26+
2627public static class Solution2 {
28+ /**
29+ * use heap data structure
30+ */
31+ public int kthSmallest (int [][]matrix ,int k ) {
32+ PriorityQueue <int []>heap =new PriorityQueue <>((a ,b ) ->Integer .compare (a [0 ],b [0 ]));
33+ for (int i =0 ;i <Math .min (matrix .length ,k );i ++) {
34+ //we store value, rowIndex, colIndex as an array into this heap
35+ heap .offer (new int []{matrix [i ][0 ],i ,0 });
36+ }
37+ while (k -- >1 ) {
38+ int []min =heap .poll ();
39+ if (min [2 ] +1 <matrix [min [1 ]].length ) {
40+ heap .offer (new int []{matrix [min [1 ]][min [2 ] +1 ],min [1 ],min [2 ] +1 });
41+ }
42+ }
43+ return heap .poll ()[0 ];
44+ }
45+ }
46+
47+ public static class Solution3 {
2748/**
2849 * Binary Search : The idea is to pick a mid number, then compare it with the elements in each row, we start form
2950 * end of row util we find the element is less than the mid, the left side element is all less than mid; keep tracking elements
@@ -53,24 +74,4 @@ public int kthSmallest(int[][] matrix, int k) {
5374return lo ;
5475 }
5576 }
56-
57- public static class Solution3 {
58- /**
59- * use heap data structure
60- */
61- public int kthSmallest (int [][]matrix ,int k ) {
62- PriorityQueue <int []>heap =new PriorityQueue <>((a ,b ) ->a [0 ] -b [0 ]);
63- for (int i =0 ;i <matrix .length ;i ++) {
64- //we store value, rowIndex, colIndex as an array into this heap
65- heap .offer (new int []{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 (new int []{matrix [min [1 ]][min [2 ] +1 ],min [1 ],min [2 ] +1 });
71- }
72- }
73- return heap .poll ()[0 ];
74- }
75- }
7677}