## 题目描述：

LeetCode 378. Kth Smallest Element in a Sorted Matrix

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.

## Python代码：

class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
m, n = len(matrix), len(matrix[0])
visited = [[False] * n for _ in range(m)]
q = [(matrix[0][0], 0, 0)]
ans = None
visited[0][0] = True
for _ in range(k):
ans, i, j = heapq.heappop(q)
if i + 1 < m and not visited[i + 1][j]:
visited[i + 1][j] = True
heapq.heappush(q, (matrix[i + 1][j], i + 1, j))
if j + 1 < n and not visited[i][j + 1]:
visited[i][j + 1] = True
heapq.heappush(q, (matrix[i][j + 1], i, j + 1))
return ans

## Python代码：

class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
m, n = len(matrix), len(matrix[0])
q = [(matrix[0][0], 0, 0)]
ans = None
for _ in range(k):
ans, i, j = heapq.heappop(q)
if j == 0 and i + 1 < m:
heapq.heappush(q, (matrix[i + 1][j], i + 1, j))
if j + 1 < n:
heapq.heappush(q, (matrix[i][j + 1], i, j + 1))
return ans

## Python代码：

class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
lo, hi = matrix[0][0], matrix[-1][-1]
while lo <= hi:
mid = (lo + hi) >> 1
loc = sum(bisect.bisect_right(m, mid) for m in matrix)
if loc >= k:
hi = mid - 1
else:
lo = mid + 1
return lo

## Python代码：

class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
lo, hi = matrix[0][0], matrix[-1][-1]
while lo <= hi:
mid = (lo + hi) >> 1
loc = self.countLower(matrix, mid)
if loc >= k:
hi = mid - 1
else:
lo = mid + 1
return lo

def countLower(self, matrix, num):
i, j = len(matrix) - 1, 0
cnt = 0
while i >= 0 and j < len(matrix[0]):
if matrix[i][j] <= num:
cnt += i + 1
j += 1
else:
i -= 1
return cnt

Pingbacks已关闭。

1. aaa 发布于 2016年8月2日 05:19 #

有点问题，为什么先加下方入堆，
如果先加右方入堆呢？

2. 在线疯狂 发布于 2016年8月2日 10:46 #

实际上是对称的，把扩展方式改为：当i == 0时才向右扩展，否则只向下扩展。这样也可以