Pythonのソートされた行列のK番目の最小要素

行と列のそれぞれが昇順で並べ替えられているnxn行列があるとすると、行列内でk番目に小さい要素を見つける必要があります。これは、k番目の一意の要素ではなく、ソートされた順序でk番目に小さい要素であることに注意してください。したがって、入力が[[1,5,9]、[10,11,13]、[12,13,15]]のようである場合、k =8の場合、出力は13になります。

これを解決するには、次の手順に従います-

• checkVal（）と呼ばれる1つのメソッドを定義し、引数は行列と値です
• i：=0、j：=行列の長さ[0] – 1、カウンター：=0
• whilei<行列の長さとj>=0
  • matrix [i、j]>の値の場合、jを1減らし、それ以外の場合、counter：=counter + j + 1、iを1増やします
• リターンカウンター
• 主な方法は次のようになります-
• n：=行列の行、高：=右下隅の要素、低：=左上隅の要素
• 低い<=高い間、実行
  • 中=低+（高–低）/ 2
  • count：=checkVal（matrix、mid）
  • count
• 低く戻す

理解を深めるために、次の実装を見てみましょう-

例

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