378 kth smallest element in a sorted matrix

思路一：暴力法

class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
tmp = []
for row in matrix:
for column in row:
tmp.append(column)
tmp.sort()
return tmp[k-1] if tmp and len(tmp)>0 else None


思路二：

先来heap
1. 利用heap,先对第一行所有元素加入heap,每个元素下面同一列的元素必然比他们大
2. 重复K-1次下面的过程
• 取现在的root
• 将root下面的元素加入heap

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

heap = []
row = len(matrix)
col = len(matrix[0])

for i in range(col):
# heap store its value and location
heapq.heappush(heap, (matrix[0][i], 0, i))

print heap

for j in range(k-1):
cur = heappop(heap)
x = cur[1]
y = cur[2]
if x+1 < row:
heapq.heappush(heap, (matrix[x+1][y],x+1,y))

return heap[0][0]


思路三： heapq一行

class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
return list(heapq.merge(*matrix))[k-1]

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


apachecn/AiLearning