class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
lo = matrix[0][0]
hi = matrix[len(matrix)-1][len(matrix[0])-1]+1
while lo < hi:
mid = (lo + hi) >> 1
count = 0
j = len(matrix[0])-1
for i in range(0, len(matrix)):
while j >= 0 and matrix[i][j] > mid:
j -= 1
count += j+1
if count < k:
lo = mid+1
else:
hi = mid
return lo
Runtime: 172 ms, faster than 96.86% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix.
Memory Usage: 18.6 MB, less than 9.09% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix.
这个用来统计count的方法非常巧妙啊，利用了数组都是升序的特点。
先用一行最大的数字比较，选择行；
然后在该行向前走，找到mid；
count的值就直接通过mid的索引来求
stefanPochmann的代码优化版：
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
lo = matrix[0][0]
hi = matrix[-1][-1]
while lo < hi:
mid = (lo + hi) >> 1
count = 0
j = len(matrix[0])
for row in matrix:
while j >= 1 and row[j-1] > mid:
j -= 1
count += j
if count < k:
lo = mid+1
else:
hi = mid
return lo
Runtime: 180 ms, faster than 90.76% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix.
Memory Usage: 18.6 MB, less than 9.09% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix.
看起来更简洁了，但是更花时间😂
数学题
完全看不懂的数学题版本，评论区也是一片哀嚎，哭着点赞
感觉这应该是全leet最难的数学题了吧。。😂
class Solution(object):
def kthSmallest(self, matrix, k):
# The median-of-medians selection function.
def pick(a, k):
if k == 1:
return min(a)
groups = (a[i:i+5] for i in range(0, len(a), 5))
medians = [sorted(group)[len(group) / 2] for group in groups]
pivot = pick(medians, len(medians) / 2 + 1)
smaller = [x for x in a if x < pivot]
if k <= len(smaller):
return pick(smaller, k)
k -= len(smaller) + a.count(pivot)
return pivot if k < 1 else pick([x for x in a if x > pivot], k)
# Find the k1-th and k2th smallest entries in the submatrix.
def biselect(index, k1, k2):
# Provide the submatrix.
n = len(index)
def A(i, j):
return matrix[index[i]][index[j]]
# Base case.
if n <= 2:
nums = sorted(A(i, j) for i in range(n) for j in range(n))
return nums[k1-1], nums[k2-1]
# Solve the subproblem.
index_ = index[::2] + index[n-1+n%2:]
k1_ = (k1 + 2*n) / 4 + 1 if n % 2 else n + 1 + (k1 + 3) / 4
k2_ = (k2 + 3) / 4
a, b = biselect(index_, k1_, k2_)
# Prepare ra_less, rb_more and L with saddleback search variants.
ra_less = rb_more = 0
L = []
jb = n # jb is the first where A(i, jb) is larger than b.
ja = n # ja is the first where A(i, ja) is larger than or equal to a.
for i in range(n):
while jb and A(i, jb - 1) > b:
jb -= 1
while ja and A(i, ja - 1) >= a:
ja -= 1
ra_less += ja
rb_more += n - jb
L.extend(A(i, j) for j in range(jb, ja))
# Compute and return x and y.
x = a if ra_less <= k1 - 1 else \
b if k1 + rb_more - n*n <= 0 else \
pick(L, k1 + rb_more - n*n)
y = a if ra_less <= k2 - 1 else \
b if k2 + rb_more - n*n <= 0 else \
pick(L, k2 + rb_more - n*n)
return x, y
# Set up and run the search.
n = len(matrix)
start = max(k - n*n + n-1, 0)
k -= n*n - (n - start)**2
return biselect(range(start, min(n, start+k)), k, k)[0]