
Viết một thuật toán để tìm kiếm một giá trị target
trong một ma trận m x n
.
Ma trận có 2 đặc điểm:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
Ví dụ, ở ma trận trên:
5
thì kết quả trả về là true
20
thì kết quả trả về là false
true
. Khi bạn duyệt tới hết ma trận m x n
mà vẫn chưa tìm được giá trị cần tìm, thì trả về false
m
), và mỗi hàng duyệt qua từng cột (n
) nên độ phức tạp thuật toán về mặt thời gian sẽ là O(m x n)
bool searchMatrix(vector<vector<int>>& matrix, int target) { int rows = matrix.size(); if (rows == 0) return false; int columns = matrix[0].size(); for(int r = 0; r < rows; r++) { for (int c = 0; c < columns; c++) { if (matrix[r][c] == target) { return true; } } } return false; }
ý tưởng: vì mỗi hàng đã được sắp xếp theo chiều tăng dần rồi, bạn có thể duyệt từng hàng, và áp dụng tìm kiếm nhị phân để kiểm tra trong hàng đó có chứa giá trị cần tìm hay không.
độ phức tạp thuật toán: vì bạn phải duyệt từng hàng m
và với mỗi hàng, bạn áp dụng tìm kiếm nhịn phân log(n)
nên độ phức tạp thuật toán theo thời gian sẽ là O(mlog(n)
source code C++:
bool binarySearch(vector<int>& array, int c, int max_c, int target) { while(c <= max_c) { int mid = c + (max_c - c) / 2; if (array[mid] == target) { return true; } if (array[mid] > target) { max_c = mid - 1; } else { c = mid + 1; } } return false; } bool searchMatrix(vector<vector<int>>& matrix, int target) { int rows = matrix.size(); if (rows == 0) return false; int columns = matrix[0].size(); for(int r = 0; r < rows; r++) { int c = 0, max_c = columns - 1; if (binarySearch(matrix[r], c, max_c, target)) { return true; } } return false; }
ý tưởng: ở bài tập này, để tìm xem giá trị target
trong ma trận m x n
hay không, thì cần tìm xem có tồn tại 1 vị trí [i,j]
mà tại đó matrix[i][j] == target
i
, j
thay đổi theo hàng và cột. Và ma trận này đã được sắp xếp tăng dần từ trái qua phải, từ trên xuống dưới rồi, nên nếu ta có thể cố định i
hoặc j
để tìm vị trí tiếp theo của [i, j]
và kiểm tra với target
, thì có thể giảm được số lượng vị trí [i,j]
cần duyệt.[i, j]
, matrix[i][j] > target
thì target
nếu tồn tại trong ma trận m*n
thì sẽ chỉ nằm từ cột 0 -> j-1
.matrix[i][j] < target
thì target
nếu tồn tại trong ma trận m*n
thì sẽ chỉ nằm từ hàng i -> max row
.matrix[i][j] == target
, return true
i = 0, j = max_column
thì có thể giảm số lượng duyệt i, j
không cần thiết.độ phức tạp thuật toán theo thời gian là O(m + n)
source code C++:
bool searchMatrix(vector<vector<int>>& matrix, int target) { int rows = matrix.size(); if (rows == 0) return false; int columns = matrix[0].size(); int r = 0, c = columns - 1; while (r < rows && c >= 0) { if (matrix[r][c] == target) { return true; } if (matrix[r][c] > target) { c--; } else { r++; } } return false; }
Hi vọng bạn tìm được một cái gì đó mới thông qua bài viết này. Mọi thắc mắc, hoặc có sự nhầm lẫn ở bài viết, mong các bạn nhiệt tình comment ạ.
Happy coding!!!