Leetcode刷题100天—378. 有序矩阵中第 K 小的元素(优先队列)—day16

野性酷女 2022-09-11 01:19 167阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210823210555477][]

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。  
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

示例 1：

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
    输出：13
    解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

示例 2：

输入：matrix = [[-5]], k = 1
    输出：-5

提示：

*  n == matrix.length
 *  n == matrix\[i\].length
 *  1 <= n <= 300
 *  \-109 <= matrix\[i\]\[j\] <= 109
 *  题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
 *  1 <= k <= n2

> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

package 优先队列;
    
    import java.util.Comparator;
    import java.util.PriorityQueue;
    /* * 4 * https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/ */
    public class _378_有序矩阵中第K小的元素 { 
    	public int kthSmallest(int[][] matrix, int k) { 
    		
    		int[] n;
    		 
            int len = 0;
            // 计算一维数组长度
            for (int[] element : matrix) { 
                len += element.length;
            }
            // 复制元素
            n = new int[len];
            int index = 0;
            for (int[] element : matrix) { 
                for (int element2 : element) { 
                    n[index++] = element2;
                }
            }
    // 通过优先队列存入数据
            PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() { 
            	public int compare(Integer o1,Integer o2) { 
    				return o2-o1;//大顶堆
    			}
            });
    // for循环入栈
            for(int i=0;i<k;i++) { 
            	queue.offer(n[i]);
            }
    // 在for循环判断
            for(int i=k;i<n.length;i++) { 
            	if (queue.peek()>n[i]) { 
    				queue.poll();
    				queue.offer(n[i]);
    			}
            }
            return queue.peek();
    	}
    	
    // 方法二:效率有点底
    // for (int[] nums:matrix){ 
    // for(int num:nums) { 
    // if(queue.size()>=k) { 
    // if (queue.peek()>num) { 
    // queue.poll();
    // queue.offer(num);
    // }
    // }else { 
    // queue.offer(num);
    // }
    // }
    // }
    //可以通过优先队列中的大顶堆判断
    	public static void main(String[] args) { 
    
    	}
    
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210823210555477]: /images/20220829/1ab6765f49e54a82b0b1ba3327e88aa4.png