378. Kth Smallest Element in a Sorted Matrix（查找矩阵中第k小的数）

淩亂°似流年 2022-07-14 06:25 176阅读 0赞

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.

Note:

You may assume k is always valid, 1 ≤ k ≤ n2.

题目大意：给定一个n\*n的矩阵，每一行，每一列都按照升序排列。查找矩阵中第k小的数。

解题思路：

解法一：对所有元素排序，返回第k小的数。但是貌似就算使用堆排序都会超时，还是贴上代码：

public class Solution {
        public int kthSmallest(int[][] matrix, int k) {
    		int n = matrix.length;
    		int[] nums = new int[n * n + 1];
    		int index = 0;
    		for (int i = 0; i < n; i++)
    			for (int j = 0; j < n; j++)
    				nums[++index] = matrix[i][j];
    		for (int i = index / 2; i > 0; i++) {
    			adjustDown(nums, index, n);
    		}
    		while(k>1){
    			nums[1] = nums[n];
    			n--;
    			adjustDown(nums, index, n);
    		}
    		return nums[0];
    	}
    
    	public void adjustDown(int[] nums, int index, int n) {
    		int i;
    		nums[0] = nums[index];
    		for (i = index * 2; i <= n; i *= 2) {
    			if (i < n && nums[i] > nums[i + 1])
    				i++;
    			if (nums[i] >= nums[0])
    				break;
    			else{
    				nums[index] = nums[i];
    				index = i;
    			}
    		}
    		nums[index] = nums[0];
    	}
    }

解法二：使用优先队列。代码如下：（31ms，beats 45.40%）

public class Solution {
        class Tuple implements Comparable<Tuple>{
    		int x;
    		int y;
    		int val;
    		public Tuple(int x, int y, int val) {
    			super();
    			this.x = x;
    			this.y = y;
    			this.val = val;
    		}
    		@Override
    		public int compareTo(Tuple o) {
    			// TODO Auto-generated method stub
    			return val-o.val;
    		}
    	}
    	
    	public int kthSmallest(int[][] matrix, int k) {
    		PriorityQueue<Tuple> queue = new PriorityQueue<>();
    		int n = matrix.length;
    		Tuple tuple = null;
    		for(int j=0;j<n;j++)
    			queue.add(new Tuple(0, j, matrix[0][j]));
    		while(k-->1){
    			tuple = queue.poll();
    			if(tuple.x!=n-1){
    				tuple = new Tuple(tuple.x+1,tuple.y,matrix[tuple.x+1][tuple.y]);
    				queue.add(tuple);
    			}
    		}
    		tuple = queue.poll();
    		return tuple.val;
    	}
    }