Kth Smallest Element in a Sorted Matrix

用堆的方法很容易想到，O(klgn)的时间复杂度

class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        n = len(matrix)
        if not n:
            return 0

        m = len(matrix[0])
        if not m:
            return 0

        heap = [(matrix[0][0], 0, 0)]
        checker = set()
        checker.add((0, 0,))
        result = None
        while k:
            value, i, j = heapq.heappop(heap)
            result = value
            k -= 1
            if i + 1 < n and (i + 1, j) not in checker:
                checker.add((i + 1, j,))
                heapq.heappush(heap, (matrix[i + 1][j], i + 1, j,))
            if j + 1 < m and (i, j + 1) not in checker:
                checker.add((i, j + 1,))
                heapq.heappush(heap, (matrix[i][j + 1], i, j + 1,))

        return result