给定一个 n x n
矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k
小的元素。
请注意,它是排序后的第 k
小元素,而不是第 k
个不同的元素。
示例:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
提示:
你可以假设 k 的值永远是有效的,1 ≤ k ≤ n2 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
利用其每一行都是递增的这一特性,我们可以知道当前最小的元素一定在所有行的第一个元素之中,因此一个做法为每次从每一行第一个元素中找到最小的元素删除他,如此进行k次,第k次删除的元素即为所求。若直接进行这种做法时间复杂度为O(k * N),其中N为矩阵的边长,需要找k次每次需要遍历一遍矩阵的一列。
因此我们想到可以使用一个小根堆来优化找最小值的过程,堆的初值为将第一列元素存进去,每次从堆中弹出一个元素,弹出的是哪一行的就把那行当前位置元素存入堆中。如此每次只需要O(logN)的时间复杂度总体时间复杂度为O(k * log(N))。
实现代码如下:
class Solution {
public static class Node{
int index;
int val;
public Node(int index, int val){
this.index = index;
this.val = val;
}
}
public static class NodeComparator implements Comparator<Node>{
public int compare(Node n1, Node n2){
return n1.val - n2.val;
}
}
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int[] next = new int[n]; // next[i] 为第i行开始元素下标
Queue<Node> minHeap = new PriorityQueue<>(new NodeComparator());
for(int i = 0; i < n; i++){
minHeap.add(new Node(i, matrix[i][next[i]++]));
}
int result = -1;
while(k > 0){
Node cur = minHeap.remove();
k--;
result = cur.val;
if(next[cur.index] < n){
minHeap.add(new Node(cur.index, matrix[cur.index][next[cur.index]++] ) );
}
}
return result;
}
}
对值进行二分,下界为left = matrix[0] [0],上界为right = matrix[n - 1] [n - 1]。每次统计小于mid的数目记做count,
若count小于等于k则说明待求值在mid右侧(不包括mid),left = mid + 1;
若count大于k,则说明待求值在mid左侧(包括mid) ,right = mid。
此外对于如何统计小于mid的数目,可以从左下角的位置开始遍历,
若当前值小于等于mid,则证明其上的所有值都小于等于mid,统计数目并左移
若当前值大于mid,则证明该行从当前位置开始均大于mid,上移动。
时间复杂度为O(log(max- min)* N),其中max为矩阵中的最大值,min为矩阵中的最小值,N为矩阵的边长。实现代码如下:
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int left = matrix[0][0];
int right = matrix[matrix.length - 1][matrix.length - 1];
while(left < right){
int mid = left + (right - left) / 2;
int num = getNum(matrix, mid);
if(num >= k){
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
public int getNum(int[][] matrix, int mid){ // 获得小于等于mid 的值的数目
int count = 0;
int i = matrix.length - 1;
int j = 0;
while(i >= 0 && j < matrix.length){
if(matrix[i][j] <= mid){
count += i + 1; // 一次计算一列的数目
j++;
}else{
i--;
}
}
return count;
}
}