378. Kth Smallest Element in a Sorted Matrix

解題說明

C++ 解法

複雜度分析

虛擬碼

Function kthSmallest(matrix, k):
  n = number of rows (= number of columns)
  left = matrix[0][0]
  right = matrix[n-1][n-1]

  While left < right:
    mid = left + (right - left) / 2
    count = 0
    For each row in matrix:
      count += number of elements <= mid in this row  // use upper_bound
    If count < k:
      left = mid + 1   // answer is strictly greater than mid
    Else:
      right = mid      // mid might be the answer or too large

  Return left

其他解法

延伸思考