Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/search-a-2d-matrix/
Table of Contents
1. Cách tiếp cận vấn đề
Bài toán này có cách tiếp cận y hệt bài toán: 704. Binary Search. Chỉ khác là mảng input được cung cấp dưới dạng 2D thay vì 1D, mảng 2D matrix bao gồm m x n phần tử (m là số lượng dòng, còn n là số lượng cột):
- Cách phần tử trong 1 hàng được sắp xếp theo thứ tự không giảm.
- Phần tử đầu tiên của mỗi hàng sẽ lớn hơn phần tử cuối cùng của hàng trước đó.
Cho trước số nguyên target, trả về true nếu target xuất hiện trong mảng matrix và ngược lại.
Và bài toán yêu cầu chúng ta phải giải nó với time-complexity là O(log(m*n)). Tức là không được tìm kiếm tuyến tính Linear Search vì nó sẽ có time-complexity là O(m*n)
Ví dụ:
- Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
- Output: true
Ta sẽ xem mảng 2D này như mảng 1D và áp dụng binary search lên nó với left index = 0 còn right index = m * n - 1. Tuy nhiên vấn đề lớn nhất là khi ta tính toán và có được giá trị mid rồi, thì làm sao biết được giá trị mid đó đang nằm ở vị trí nào của mảng 2D (cần x và y để xác định).
2. Solution & Phân Tích
Ta gọi số lượng các phần tử trong 1 hàng hay số lượng các cột là n. Để biết được giá trị mid đang ở cột nào và hàng nào, ta chỉ cần áp dụng công thức sau:
- Vị trí hàng = mid / n
- Vị trí cột = mid % n
Từ đó ta có thể lấy ra được giá trị tại mid ở trong mảng 2D và áp dụng các quy tắc tương tự như binary search ở mảng 1D.
Time-Complexity: O(log(m*n))
Space-Complexity: O(1) - In-place algorithm
Với m là số lượng dòng, còn n là số lượng cột
3. Code
Tương tự như bài 1D, sử dụng mid = left + (right - left) / 2; như 1 best practice để tránh tràn số.
