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.

 

#! /usr/bin/evn python
#coding:utf-8

from heapq import heappush, heappop

class MinQ(object):
    def __init__(self):
        self.h = []
    
    def push(self, value):
        heappush(self.h, value)
    
    def pop(self):
        return heappop(self.h)


class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        assert matrix
        rows_cnt = len(matrix)
        min_q = MinQ()
        for j,c in enumerate(matrix[0]):
            min_q.push([c, 0, j])
        n = 1
        val = None
        while n <= k:
            val = min_q.pop()
            i,j = val[1]+1, val[2]
            if i < rows_cnt:
                min_q.push([matrix[i][j], i, j])
            n += 1
        return val[0]

骚年，牢记最小堆的实现！

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6