Python 中排序矩陣的第 K 小元素

假設我們有一個 n x n 的矩陣，其中每一行和每一列都按升序排序，我們需要找到矩陣中第 k 小的元素。請注意，它是按排序順序排列的第 k 個最小元素，而不是第 k 個唯一元素。例如，如果輸入為 [[1,5,9],[10,11,13],[12,13,15]]，如果 k = 8，則輸出將為 13。

為了解決這個問題，我們將遵循以下步驟 -

  • 定義一個名為 checkVal() 的方法，其引數為矩陣和值
  • i := 0，j := matrix[0] 的長度 - 1，counter := 0
  • 當 i < 矩陣的長度且 j >= 0 時
    • 如果 matrix[i, j] > value，則將 j 減 1，否則 counter := counter + j + 1，將 i 加 1
  • 返回 counter
  • 主方法將如下所示 -
  • n := 矩陣的行數，high := 右下角元素，low := 左上角元素
  • 當 low <= high 時，執行
    • mid = low + (high – low)/2
    • count := checkVal(matrix, mid)
    • 如果 count < k，則 low := mid + 1，否則 high := mid – 1
  • 返回 low

讓我們看一下以下實現，以便更好地理解 -

示例

 線上演示

class Solution(object):
   def kthSmallest(self, matrix, k):
      """
      :type matrix: List[List[int]]
      :type k: int
      :rtype: int
      """
      n = len(matrix)
      high = matrix[n-1][n-1]
      low = matrix[0][0]
      while low<=high:
         mid = low + (high - low) /2
         count = self.check_value(matrix,mid)
         if count< k:
            low = mid+1
         else :
            high = mid-1
      return int(low)
   def check_value(self, matrix, value):
      i = 0
      j = len(matrix[0])-1
      counter = 0
      while(i<len(matrix) and j >=0):
         if matrix[i][j] > value:
            j-=1
         else:
            counter+=j+1
            i+=1
      return counter
matrix = [[1,5,9],[10,11,13],[12,13,15]]
ob = Solution()
print(ob.kthSmallest(matrix, 8))

輸入

matrix =[[1,5,9],[10,11,13],[12,13,15]]
k = 8

輸出

13

更新於: 2020年4月30日

348 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告