import java.util.PriorityQueue;

public class _378 {
    static class Solution1 {
        public int kthSmallest(int[][] matrix, int k) {
            //二分查找
            //不断探测 元素的值
            //统计小于当前元素的值,由于行列有序可以快速统计，时间复杂最坏情况下(m + n);
            //由于存在重复元素
            //所以 第k个元素一定存在在 (count(x) < k, count[y]>=k]中
            int m = matrix.length;
            int n = matrix[0].length;
            int l = matrix[0][0];
            int r = matrix[m - 1][n - 1];
            while (l < r) {
                int count = 0;
                int j = n - 1;
                int mid = l + (r - l) / 2;
                for (int i = 0; i < m; i++) {
                    while (j >= 0 && matrix[i][j] > mid) j--;
                    count += (j + 1);
                }
                if (count >= k) r = mid;
                else l = mid + 1;
            }
            return r;
        }
    }

    static class Solution2 {
        public int kthSmallest(int[][] matrix, int k) {
            // [i,j,value]
            //优先队列，先出最小的，然后按照列，比最小的小的元素入队列，再出最小的，以此类推
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
                if (a[2] == b[2]) {
                    return -1;
                }
                return a[2] - b[2];
            });
            for (int i = 0; i < matrix[0].length; i++) {
                pq.offer(new int[]{0, i, matrix[0][i]});
            }
            int res = 0;
            while (k-- > 0) {
                int[] cur = pq.poll();
                res = cur[2];
                int next = cur[0] + 1;
                // System.out.println(String.format("i=%d,j=%d,res=%d,next=%d",cur[0],cur[1],cur[2],next));
                if (next < matrix.length) {
                    pq.offer(new int[]{next, cur[1], matrix[next][cur[1]]});
                }
            }
            return res;
        }
    }
}