378. 정렬된 행렬에서 k번째로 작은 요소
설명
각 행과 열이 오름차순으로 정렬된 n x n matrix가 주어지면 행렬에서 가장 작은 요소인 kth를 반환합니다.
kth 고유한 요소가 아니라 정렬된 순서에서 kth 가장 작은 요소입니다.
O(n2)보다 메모리 복잡성이 더 나은 솔루션을 찾아야 합니다.
예 1:
Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13
예 2:
Input: matrix = [[-5]], k = 1
Output: -5
제약:
Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13
Input: matrix = [[-5]], k = 1
Output: -5
n == matrix.length == matrix[i].length 1 <= n <= 300 109 <= matrix[i][j] <= 109 matrix의 모든 행과 열은 내림차순으로 정렬되지 않습니다. 1 <= k <= n2 솔루션
솔루션 1
직관
cnt로 셉니다.cnt ≥ k는 kth 가장 작은 숫자가 왼쪽 부분에 있음을 의미하므로 r = mid 그렇지 않으면 오른쪽 부분암호
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
int l = matrix[0][0], r = matrix[n - 1][n - 1], mid;
while (l < r) {
int mid = l + r >> 1;
int col = n - 1, cnt = 0;
for (int row = 0; row < n; row++) {
while (col >= 0 && matrix[row][col] > mid) col--;
cnt += col + 1;
}
if (cnt >= k)
r = mid;
else
l = mid + 1;
}
return l;
}
};
복잡성
Reference
이 문제에 관하여(378. 정렬된 행렬에서 k번째로 작은 요소), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/jiangwenqi/378-kth-smallest-element-in-a-sorted-matrix-1i53텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
