原題
在一個(gè)排序矩陣中找從小到大的第 k 個(gè)整數(shù)展运。
排序矩陣的定義為：每一行遞增，每一列也遞增透硝。
樣例
給出 k = 4和一個(gè)排序矩陣：
[
[1 ,5 ,7],
[3 ,7 ,8],
[4 ,8 ,9],
]
返回 5数焊。
解題思路
- 首先把左上角的元素放入minHeap中，進(jìn)入while循環(huán)膨处，每次pop一個(gè)最小值见秤，然后把該位置右邊和下班的值+坐標(biāo)放入minHeap中。k減一真椿，當(dāng)k等于0時(shí)鹃答，返回當(dāng)前的值
- 同時(shí)要注意，另外開一個(gè)二維數(shù)組記錄哪些元素已經(jīng)被訪問過，因?yàn)橥粋€(gè)元素可能在A的下面和B的右面
完整代碼
import Queue
class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
exist = [[False for i in range(len(matrix[0]))] for j in range(len(matrix))]
q = Queue.PriorityQueue()
q.put((matrix[0][0], 0, 0))
exist[0][0] = True
while k > 0:
cur, x, y = q.get()
if x + 1 < len(matrix) and not exist[x+1][y]:
q.put((matrix[x+1][y], x+1, y))
exist[x+1][y] = True
if y + 1 < len(matrix[0]) and not exist[x][y+1]:
q.put((matrix[x][y+1], x, y+1))
exist[x][y+1] = True
k -= 1
return cur
