kth smallest element in a sorted matrix

fishercoder1534 · fishercoder1534 · commit bf45d70983ce · 2016-07-31T18:22:40.000-07:00
diff --git a/MEDIUM/src/medium/KthSmallestElementInASortedMatrix.java b/MEDIUM/src/medium/KthSmallestElementInASortedMatrix.java
@@ -0,0 +1,41 @@
+package medium;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+/**378. Kth Smallest Element in a Sorted Matrix  QuestionEditorial Solution  My Submissions
+Total Accepted: 5
+Total Submissions: 7
+Difficulty: Medium
+Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
+
+Note that it is the kth smallest element in the sorted order, not the kth distinct element.
+
+Example:
+
+matrix = [
+   [ 1,  5,  9],
+   [10, 11, 13],
+   [12, 13, 15]
+],
+k = 8,
+
+return 13.
+Note: 
+You may assume k is always valid, 1 ≤ k ≤ n2.*/
+public class KthSmallestElementInASortedMatrix {
+    //brute force made it AC'ed, extreme test case needed for OJ
+    public int kthSmallest(int[][] matrix, int k) {
+        List<Integer> list = new ArrayList<Integer>();
+        int n = matrix.length;
+        for(int i = 0; i < n; i++){
+            for(int j = 0; j < n; j++){
+                list.add(matrix[i][j]);
+            }
+        }
+        Collections.sort(list);
+        return list.get(k-1);
+    }
+    
+    //TODO: use heap and binary search to do it.
+}
