Python에서 정렬된 행렬의 K번째 가장 작은 요소

<시간/>

각 행과 열이 오름차순으로 정렬된 n x n 행렬이 있다고 가정하면 행렬에서 k번째로 작은 요소를 찾아야 합니다. k번째 고유 요소가 아니라 정렬된 순서에서 k번째로 작은 요소입니다. 따라서 입력이 [[1,5,9],[10,11,13],[12,13,15]]와 같으면 k =8이면 출력은 13이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

checkVal()이라는 메서드를 정의하고 인수는 행렬과 값입니다.
i :=0, j :=행렬의 길이[0] – 1, 카운터 :=0
동안 i <행렬의 길이 및 j>=0
- 행렬[i, j]> 값이면 j를 1만큼 감소, 그렇지 않으면 counter :=counter + j + 1, i를 1만큼 증가
반품 카운터
주요 방법은 다음과 같습니다 -
n :=행렬의 행, high :=오른쪽 하단 모서리 요소, low :=왼쪽 상단 모서리 요소
낮은 동안 <=높음, do
- 중간 =낮음 + (높음 – 낮음)/2
- count :=checkVal(행렬, 중간)
- 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