2018-08-08 leetcode 378 Kth Smal

Description:
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.

解题思路：
利用minheap来解决， 将这些数字放进堆里， 弹出k次 那么就能得到题目想要的数字。

1. 将第一行的所有元素放入heap里。
2. 循环k-1次：
   每一次将最小的元素弹出， 因此需要知道每个元素的在矩阵中的坐标， （可以建立一个类来存放）。然后将被弹出元素的同一列的下一个元素放入heap里。
   （该思路参考leetcode答案里的Share my thoughts and Clean Java Code
   ）

class Solution {
        public int kthSmallest(int[][] matrix, int k) {
            PriorityQueue<Tuple> queue = new PriorityQueue<>();
            int n = matrix.length;
            for(int i = 0; i < n; i++)
                queue.offer(new Tuple(0, i, matrix[0][i]));
            for(int i = 0; i < k - 1; i++)
            {
                Tuple t = queue.poll();
                if(t.x == n - 1) continue;
                queue.offer(new Tuple(t.x+1, t.y, matrix[t.x+1][t.y]));

            }

            return queue.poll().val;
        }

        class Tuple implements Comparable<Tuple> {
            private int x;
            private int y;
            private int val;

            public Tuple(int x, int y, int val)
            {
                this.x = x;
                this.y = y;
                this.val = val;

            }

            @Override
            public int compareTo(Tuple that)
            {
                return this.val - that.val;

            }


        }

    }