首页 > 代码库 > 378. Kth Smallest Element in a Sorted Matrix
378. Kth Smallest Element in a Sorted Matrix
和merge k sorted linked list是一样的,不同就是自己要打一个包建一个类,然后建一个pq
1 class Node{ 2 int x; 3 int y; 4 int val; 5 public Node(int x, int y, int val) { 6 this.x = x; 7 this.y = y; 8 this.val = val; 9 } 10 } 11 12 public int kthSmallest(int[][] matrix, int k) { 13 if(matrix.length == 0 || matrix[0].length == 0) { 14 return 0; 15 } 16 int row = matrix.length; 17 int col = matrix[0].length; 18 PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() { 19 public int compare(Node n1, Node n2) { 20 return n1.val - n2.val; 21 } 22 }); 23 for(int i = 0; i < matrix.length; i++) { 24 pq.offer(new Node(i, 0, matrix[i][0])); 25 } 26 while(k > 1) { 27 Node node = pq.poll(); 28 k--; 29 if(node.y < row - 1) { 30 pq.offer(new Node(node.x, node.y + 1, matrix[node.x][node.y + 1])); 31 } 32 } 33 return pq.poll().val; 34 }
时间复杂度是O(klogn). n = matrix.length
378. Kth Smallest Element in a Sorted Matrix
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。