Giả sử chúng ta có một ma trận n x n trong đó mỗi hàng và cột được sắp xếp theo thứ tự tăng dần, chúng ta phải tìm phần tử nhỏ nhất thứ k trong ma trận. Lưu ý rằng nó là phần tử nhỏ nhất thứ k trong thứ tự đã sắp xếp, không phải là phần tử duy nhất thứ k. Vì vậy, nếu đầu vào là [[1,5,9], [10,11,13], [12,13,15]], nếu k =8, thì đầu ra sẽ là 13.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- xác định một phương thức được gọi là checkVal () và các đối số là ma trận và giá trị
- i:=0, j:=độ dài của ma trận [0] - 1, bộ đếm:=0
- while i <độ dài của ma trận và j> =0
- if ma trận [i, j]> value, sau đó giảm j đi 1, ngược lại counter:=counter + j + 1, tăng i lên 1
- bộ đếm trả lại
- phương thức chính sẽ giống như -
- n:=hàng của ma trận, cao:=phần tử góc dưới cùng bên phải, thấp:=phần tử góc trên cùng bên trái
- trong khi thấp <=cao, thực hiện
- mid =low + (high - low) / 2
- count:=checkVal (ma trận, giữa)
- nếu count
- trả về mức thấp
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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
Đầu ra
13