题目：
378. 有序矩阵中第K小的元素
给定一个 *n x n *矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
示例：
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]],
k = 8,
返回 13。
提示：
你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2。
注：本文的复杂度不一定对，我的复杂度分析一般般。
1.归并排序
因为是多个列表，所以会最先想到依次按顺序归并排序，代码如下。
复杂度为O(n)，和k没关系，因为是完全排完序之后取第k个值。一般递归归并排序的复杂度是O(nlogn)，但是这里是有序的，所以复杂度有所降低。如果使用两两归并的话，复杂度变为O(nlogk)
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
if len(matrix)==0:
return None
res = matrix[0]
for i in range(1,len(matrix)):
res = self.sortMerge(res,matrix[i])
return res[k-1]
def sortMerge(self,arr1,arr2):
i = 0
j = 0
res_arr = []
while i<len(arr1) and j <len(arr2):
if arr1[i]<=arr2[j]:
res_arr.append(arr1[i])
i+=1
else:
res_arr.append(arr2[j])
j+=1
while i<len(arr1):
res_arr.append(arr1[i])
i+=1
while j<len(arr2):
res_arr.append(arr2[j])
j+=1
return res_arr
2.多指针
但是有序的情况下应该还有其他方法，思考一下。一般情况，找第k小或者第K大的元素用堆排序还挺好，但是这里本身就是有序的，所以堆排序的话，就有点浪费。可以对每行没有被取走的最小元素进行排序，每次取走一个，假设行数为k，给出k个指针即可。每次比较是O(n)，进行k次，O(nk)，n行。
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
pointer = [0 for i in range(len(matrix))]
arr_sorted = []
for j in range(k):
low = float("inf")
rownumber = 0
for i in range(len(matrix)):
if pointer[i] >=len(matrix[0]):
pass
else:
if matrix[i][pointer[i]] <=low:
low = matrix[i][pointer[i]]
rownumber = i
pointer[rownumber]+=1
arr_sorted.append(low)
return arr_sorted[k-1]
3.堆排序（只对每行最小元素）
对上面的思想进一步优化，利用最小堆，极大的提高比较的速度，也能记录行列值。这个堆是无序堆，不会浪费，因为他不是对全部元素。堆的复杂度是O(logn)，所以这里是O(klogn)，n行。
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
n = len(matrix)
pq = [(matrix[i][0], i, 0) for i in range(n)]
#构造一个最小堆,也就是将元素的位置挪动一下
heapq.heapify(pq)
ret = 0
#弹出k-1次
for i in range(k - 1):
#弹出堆顶元素，记录堆顶元素所处的行数x和列数y
num, x, y = heapq.heappop(pq)
if y != n - 1:
#如果不是最后一个元素那么继续插入，弹出元素的下一个元素
heapq.heappush(pq, (matrix[x][y + 1], x, y + 1))
#弹出小的数x
return heapq.heappop(pq)[0]
matrix = [ [ 1, 5, 9],[10, 11, 13], [12, 13, 15]]
s = Solution()
s.kthSmallest(matrix,8)
4.二分查找
有序条件下二分查找是很有用的方法，所以尝试利用二分查找，复杂度O(logn)。也可以普通查找，复杂度为O(n)。
class Solution:
def kthSmallest(self, matrix, k):
n = len(matrix)
left = matrix[0][0]
right = matrix[-1][-1]
while left<right:
print(left,right)
mid = int((left+right)/2)
if self.check(matrix,mid,k,n):
left = mid+1
else:
right = mid
return left
def check(self,matrix,mid,k,n):
#判断mid之前有多少个，如果少于k，那么mid取右边
i = n-1
count = 0
j=0
while i>=0 and j <n:
#每列每列的比较
if mid >=matrix[i][j]:
count += i+1
j += 1
else:
i -= 1
return count<k
matrix = [ [ 1, 5, 9],[10, 11, 13], [12, 13, 15]]
s = Solution()
s.kthSmallest(matrix,8)
