Giả sử có ma trận n x n, mỗi hàng và cột được sắp xếp tăng dần, ta phải tìm phần tử nhỏ thứ K trong ma trận. Lưu ý là phần tử nhỏ thứ K theo thứ tự sắp xếp, không phải phần tử duy nhất thứ K. Nếu đầu vào [[1,5,9],[10,11,13],[12,13,15]], k = 8, kết quả 13.
Để giải quyết, ta làm theo các bước −
- định nghĩa phương thức checkVal(matrix, value)
- i := 0, j := len(matrix[0]) - 1, counter := 0
- khi i < len(matrix) và j >= 0
- nếu matrix[i][j] > value, giảm j 1, ngược lại counter := counter + j + 1, tăng i 1
- trả về counter
- phương thức chính:
- n := hàng matrix, high := phần tử góc dưới phải, low := phần tử góc trên trái
- khi low <= high
- mid = low + (high - low)/2
- count := checkVal(matrix, mid)
- nếu count < k, low := mid + 1, ngược lại high := mid - 1
- trả về low
Xem triển khai sau −
Ví dụ
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))
Đầu vào
matrix =[[1,5,9],[10,11,13],[12,13,15]] k = 8
Kết quả
13