74. Search a 2D Matrix
Tags:
Medium
Skills:
Binary Search
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
target có nằm trong matrix khôngApproach
binary search trên phạm vi từ 0 -> m *n - 1 , với m là số hàng và n là số cộtmid (trong mảng 1 chiều), chuyển đôi sang chỉ số 2 chiều bằngrow = Math.floor(mid / numCols) Math.floor(mid / numCols)?Giả sử bạn "trải phẳng" (flatten) ma trận 2D kích thước numRows x numCols thành một mảng 1 chiều. Khi đó:
numCols,2 * numCols,Nói chung, phần tử tại hàng i, cột j trong ma trận 2D sẽ nằm ở vị trí i * numCols + j trong mảng 1 chiều.
Ngược lại, khi biết vị trí mid trong mảng 1 chiều, để tìm ra nó nằm ở hàng nào của ma trận 2D, ta lấy:
row = Math.floor(mid / numCols)Vì:
mid cho numCols, phần nguyên chính là số lần đầy đủ của numCols trong mid, tức là số hàng đã đi qua.numCols = 4, thì các chỉ số 0-3 thuộc hàng 0, 4-7 thuộc hàng 1, 8-11 thuộc hàng 2, v.v.Tại sao không chia cho numRows?
m * n thanh mảng 1 chiều, các phần tử sẽ được lưu liên tiếp theo từng hàng. Nghĩa là, tất cả các phần tử của hàng 0 sẽ nằm trước, rồi đến hàng 1, rồi hàng 2mid ), bạn cần biết mỗi hàng có bao nhiêu phần tử. số phần tử của mỗi hàng chính là số cột numColscol = mid % numCols Time and space complexity
Solution
1function searchMatrix(matrix: number[][], target: number): boolean {
2 const num_rows = matrix.length;
3 if(num_rows === 0) return false;
4 const num_cols= matrix[0].length;
5 let left =0, right = num_rows * num_cols - 1;
6 while(left <= right) {
7 const mid = left + Math.floor((right - left) / 2);
8 const row = Math.floor(mid / num_cols);
9 const col = mid % num_cols;
10 const mid_value = matrix[row][col];
11
12 if(mid_value === target) return true
13 else if (mid_value < target) left = mid + 1;
14 else right = mid - 1;
15 }
16 return false;
17};Mục đích
Khi thực hiện binary search trên toàn bộ ma trận, ta coi ma trận như một mảng 1 chiều có kích thước num_rows * num_cols. Để truy cập giá trị thực tế trong ma trận 2 chiều, ta cần chuyển chỉ số 1 chiều (mid) về chỉ số hàng (row) và cột (col).
Cách làm
1const row = Math.floor(mid / num_cols);
2const col = mid % num_cols;Giải thích chi tiết
num_cols phần tử.mid chia cho số cột, phần nguyên của phép chia cho biết đã qua bao nhiêu hàng đầy đủ, tức là chỉ số hàng hiện tại.num_cols = 4, mid = 7, thì row = Math.floor(7/4) = 1 (tức là hàng thứ 1).Tóm lại: