378. Kth Smallest Element in a Sorted Matrix
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Chúng mình cần tìm phần tử nhỏ thứ k trong một ma trận n x n, trong đó các hàng và cột đều được sắp xếp tăng dần.
Approach - Binary Search
matrix[0][0] và lớn nhất là matrix[n-1][n-1].k bằng cách "chia đôi" khoảng giá trị từ nhỏ nhất đến lớn nhất.mid) giữa left và right.mid. Ta dùng cách duyệt từ góc dưới bên trái của ma trận:mid, thì tất cả các phần tử phía trên nó (trong cùng cột) cũng ≤ mid. Ta cộng số lượng đó vào kết quả và di chuyển sang cột tiếp theo.mid, ta di chuyển lên hàng phía trên.mid lớn hơn hoặc bằng k, thì thu hẹp khoảng tìm kiếm về bên trái (right = mid).k, thì thu hẹp khoảng tìm kiếm về bên phải (left = mid + 1).Cần biết cách đếm số nhỏ hơn khi dùng binary search
Solution
1function kthSmallest(matrix: number[][], k: number): number {
2 const n = matrix.length;
3
4 function countLessOrEqual(mid: number): number {
5 let count = 0;
6 let row = n - 1
7 let col = 0
8
9 while (row >= 0 && col < n) {
10 if (matrix[row][col] <= mid) {
11 count += row + 1
12 col++
13 } else {
14 row--
15 }
16 }
17
18 return count;
19 }
20
21 let left = matrix[0][0]
22 let right = matrix[n - 1][n - 1]
23 while (left < right) {
24 const mid = left + Math.floor((right - left) / 2)
25 const count = countLessOrEqual(mid);
26
27 if (count < k) {
28 left = mid + 1
29 } else {
30 right = mid
31 }
32 }
33
34 return left;
35};