package 队列.优先级队列;
import java.util.Comparator;
import java.util.PriorityQueue;
/**
 * https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
 * 其中每行和每列元素均按升序排序
 * 
 * @author Huangyujun
 *
 */
public class _378_有序矩阵中第K小的元素 {
    // 优先队列
    // 方法二：优先队列
    /**
     * 思路一：先在大根堆组里放上k 个数，然后遍历后边所有数据，数据 小于堆顶，替换到k个数里，然后，最后可以得到的是 不断地用小的数去替换，这k个数据变成了小数组
     * @param matrix
     * @param k
     * @return
     */
    public int kthSmallest1(int[][] matrix, int k) {
        PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1; // 注意java中 升序是 o1 - o2【小根堆】, 降序才是 o2 - o1【大根堆】
            }
        });
        int len = matrix[0].length;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (pQueue.size() < k) {
                    pQueue.add(matrix[i][j]);
                } else if ( matrix[i][j] < pQueue.peek()) {
                    pQueue.remove();
                    pQueue.add(matrix[i][j]);
                }
            }
        }
        return pQueue.peek();
    }
    /**
     * 思路二：就是量到了k 之后，进来调整，然后poll掉一个最小的【最后留下的也肯定是最大的那些数据呀】
     * @param matrix
     * @param k
     * @return
     */
    public int kthSmallest(int[][] matrix, int k) { 
        //大根堆
          PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        int len = matrix[0].length;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                //先直接放入数据的，然后 不断地poll，最终留下的数据就是最大组那批数据啦
                queue.add(matrix[i][j]);
                if (queue.size() > k) {
                    queue.poll();
                }
            }
        }
        return queue.peek();
    }
}