p378

发表于 | 分类于 |

LeetCode 378 Kth Smallest Element in a Sorted Matrix 题解

1.题目：

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.

题意：

给一个二维数组，每一行都是有序的（仅限于此行）所以整个数组不是蛇形的。
求第K小的数。

2.解题思路:

如下的解题方法，时间复杂度还是有点高捂脸。我使用优先队列，构造了一个堆。
一直维护这个堆的大小为k,最后弹出最大的那个数，就是第k小的数。
最后TUT虽然ac了,时间复杂度还是高了捂脸。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 

public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int len = matrix.length;
		int count = 1;
		PriorityQueue<Integer> queue=new PriorityQueue<Integer>(k,new Comparator<Integer>() {
		
			@Override
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				return o2-o1;
			}
		});
		int min=Math.min(len, k);//小小优化
		for (int i = 0; i < min; i++) {
			for (int j=0;j<min;j++)
			{
				queue.offer(matrix[i][j]);
				if (queue.size()>k)
					queue.poll();

			}
		}
		return queue.peek();
		
    }
}

4.一些总结：//其他实现的可能性？