Search a 2D Matrix
Bạn nhận được một lưới số nguyên matrix có m hàng và n cột, cùng một số nguyên target. Mỗi hàng được sắp xếp theo thứ tự tăng dần, và giá trị đầu tiên của mỗi hàng lớn hơn giá trị cuối cùng của hàng phía trên. Trả về true nếu target xuất hiện trong lưới, ngược lại trả về false, trong thời gian O(log(m × n)).
Hàm
- matrixinteger-2d-array
- lưới, được biểu diễn dưới dạng danh sách các hàng, sắp xếp theo từng hàng
- targetinteger
- giá trị cần tìm
- Trả vềboolean
- true nếu target nằm trong lưới, false nếu không
Ràng buộc
1 ≤ m, n ≤ 100, trong đóm = matrix.lengthvàn = matrix[i].length- Mỗi hàng đều có cùng độ dài
n. -104 ≤ matrix[i][j], target ≤ 104- Mỗi hàng được sắp xếp theo thứ tự tăng dần nghiêm ngặt, và giá trị đầu tiên của mỗi hàng lớn hơn giá trị cuối cùng của hàng trước đó.
Ví dụ
- Đầu vào
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- Đầu ra
- true
- Giải thích
- Đọc từng hàng, 12 giá trị tạo thành một danh sách đã được sắp xếp. Tìm kiếm nhị phân trong các vị trí từ 0 đến 11 kiểm tra 21 ở vị trí 5 (quá nhỏ), 33 ở vị trí 8 (quá lớn), rồi tìm thấy 26 ở vị trí 6.
- Đầu vào
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- Đầu ra
- false
- Giải thích
- 16 sẽ nằm sau 14, giá trị cuối cùng của hàng 0, và trước 17, giá trị đầu tiên của hàng 1. Không có gì nằm giữa chúng, nên 16 không nằm trong lưới.
Câu hỏi mở rộng
Giả sử các hàng có thể có độ dài khác nhau nhưng vẫn được sắp xếp nối tiếp nhau. Bạn sẽ chuyển một vị trí thành hàng và cột như thế nào, và chi phí tìm kiếm là bao nhiêu?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Đọc ma trận theo từng hàng, từ trái sang phải, như thể đó là một danh sách dài. Bạn nhận thấy điều gì về thứ tự các giá trị trong danh sách đó?
Kết hợp lại, hai quy tắc này có nghĩa là toàn bộ ma trận, đọc theo từng hàng, tạo thành một danh sách đã sắp xếp gồm
m × ngiá trị. Bạn có thể tìm kiếm nhị phân trong danh sách đó mà không cần tạo danh sách.Tìm kiếm nhị phân trong các vị trí từ
0đếnm × n - 1. Vị trípnằm ở hàngp / nvà cộtp % n(phép chia lấy phần nguyên), vì vậy mỗi bước đọc một ô và loại bỏ một nửa số vị trí còn lại.
Lời giải
Kết hợp lại, hai quy tắc sắp xếp tạo thành một danh sách đã sắp xếp gồm m × n giá trị, khi đọc theo từng hàng. Dùng tìm kiếm nhị phân (binary search) để tìm trong danh sách đó theo vị trí, rồi chuyển mỗi vị trí thành một hàng và một cột bằng một phép chia. Khi đó, một lưới 100 nhân 100 chỉ cần tối đa 14 lần so sánh thay vì 10000.
Kiểm tra từng ô
Ý tưởng
So sánh từng ô với target và trả về true nếu khớp, false sau khi kiểm tra ô cuối cùng. Cách này đọc từng ô nên luôn đúng với mọi lưới, dù có được sắp xếp hay không. Cách này không tận dụng thứ tự, nên lưới có kích thước 100 nhân 100 cần tối đa 10000 phép so sánh.
Thuật toán
- Với mỗi hàng của
matrix, lần lượt xem từng giá trị. - Nếu giá trị bằng
target, trả vềtrue. - Sau các vòng lặp, trả về
false.
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return FalseĐi từ góc trên bên phải
Ý tưởng
Từ ô trên cùng bên phải, mọi giá trị ở bên trái đều nhỏ hơn, còn mọi giá trị bên dưới đều lớn hơn. Nếu ô đó lớn hơn target, cột bên dưới nó cũng lớn hơn: đi sang trái và bỏ cột đó. Nếu ô đó nhỏ hơn, hàng bên trái nó cũng nhỏ hơn: đi xuống và bỏ hàng đó.
Trong ví dụ đầu tiên, 14 nhỏ hơn 26, nên đi xuống 30. 30 lớn hơn, nên đi sang trái đến 26, khớp. Mỗi bước loại bỏ một hàng hoặc một cột, vì vậy bạn thực hiện nhiều nhất m + n bước: 200 bước cho một lưới 100 nhân 100. Cách di chuyển này chỉ cần các hàng và cột được sắp xếp, nên bỏ qua một nửa thông tin mà lưới này cung cấp.
Thuật toán
- Bắt đầu ở hàng
0và cột cuối cùng. - Trong khi hàng và cột vẫn nằm trong lưới, hãy đọc ô đó.
- Nếu giá trị của ô bằng
target, hãy trả vềtrue. - Nếu giá trị lớn hơn, di chuyển sang trái một cột; nếu nhỏ hơn, di chuyển xuống một hàng.
- Khi ra khỏi lưới, hãy trả về
false.
def searchMatrix(matrix, target):
# Start at the top-right corner: left is smaller, down is larger.
r, c = 0, len(matrix[0]) - 1
while r < len(matrix) and c >= 0:
value = matrix[r][c]
if value == target:
return True
if value > target:
c -= 1 # every value below in this column is larger still
else:
r += 1 # every value to the left in this row is smaller still
return FalseTìm kiếm nhị phân trên lưới đã làm phẳng
Ý tưởng
Đánh số các ô theo từng hàng: hàng 0 chứa các vị trí từ 0 đến n - 1, hàng 1 chứa từ n đến 2n - 1, cứ thế tiếp tục. Mỗi hàng được sắp xếp và bắt đầu ở vị trí ngay sau điểm kết thúc của hàng trước, nên giá trị chỉ tăng theo vị trí. Đó là một danh sách đã sắp xếp, vì vậy có thể dùng tìm kiếm nhị phân.
Bạn không cần tạo danh sách. Vị trí p nằm ở hàng p / n và cột p % n, với phép chia lấy phần nguyên. Trong ví dụ đầu tiên, n = 4, nên vị trí 6 nằm ở hàng 1, cột 2, chứa giá trị 26. Mỗi lần so sánh, số vị trí có thể chứa target giảm còn một nửa: tối đa 14 lần cho 10000 ô, với hai chỉ số dùng thêm bộ nhớ.
Thuật toán
- Gọi
mvànlần lượt là số hàng và số cột, rồi đặtlo = 0,hi = m × n - 1. - Khi
lo ≤ hi, lấymidnằm giữa hai giá trị đó. - Đọc
value = matrix[mid / n][mid % n]. - Nếu
valuebằngtarget, trả vềtrue. Nếu nhỏ hơn, đặtlo = mid + 1; nếu không, đặthi = mid - 1. - Khi vòng lặp kết thúc, trả về
false.
def searchMatrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
# Read row by row, the cells form one sorted list of rows * cols values.
# Position p of that list is matrix[p // cols][p % cols].
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
lo = mid + 1
else:
hi = mid - 1
return False
Lỗi thường gặp và trường hợp biên
- Chia cho số hàng thay vì số cột. Vị trí
pnằm ở hàngp / n; thay bằngm, code sẽ chạy đúng trên lưới vuông nhưng lỗi trên lưới có 3 hàng và 4 cột. - Trong phiên bản tìm kiếm hai lần, không xử lý trường hợp
targetnhỏ hơnmatrix[0][0]. Không hàng nào bắt đầu tại hoặc sau giá trị đó, và chỉ số hàng-1sẽ được chuyển đến lần tìm kiếm thứ hai. - Dùng vòng lặp với
lo < hikhihilà chỉ số bao gồm. Với lưới 1 × 1 chứatarget, kết quả trả về làfalsevì vòng lặp không chạy. - Trong Lua và R, quên điều chỉnh chỉ số bắt đầu từ 1: vị trí
pnằm ở hàngp / n + 1, cộtp % n + 1.
Câu hỏi thường gặp3
Độ phức tạp thời gian của bài toán Tìm kiếm trong ma trận 2D là bao nhiêu?
Tìm kiếm nhị phân trên lưới đã làm phẳng chạy trong thời gian O(log(m × n)) và dùng O(1) bộ nhớ: nhiều nhất 14 phép so sánh cho 10000 ô. Vì log(m × n) = log m + log n, cách này tương đương với việc tìm kiếm hàng trước rồi tìm bên trong hàng đó.
Bạn nên dùng cách đi từ góc trên bên phải hay tìm kiếm nhị phân?
Cách đi từ góc này sang góc kia cần O(m + n) bước và chỉ yêu cầu các hàng và cột được sắp xếp, nên cách này cũng giải được biến thể mà một hàng có thể bắt đầu thấp hơn điểm kết thúc của hàng phía trên. Khi mỗi hàng bắt đầu cao hơn điểm kết thúc của hàng trước, như ở đây, tìm kiếm nhị phân sẽ nhanh hơn.
Hai lần tìm kiếm nhị phân, một lần để tìm hàng và một lần bên trong hàng đó, cũng đúng phải không?
Có. Hãy tìm kiếm nhị phân trên cột đầu tiên để tìm hàng cuối cùng có giá trị đầu tiên không lớn hơn target, sau đó tìm kiếm nhị phân trên hàng đó. Thuật toán chạy trong O(log m + log n), với cùng độ phức tạp. Cách tìm kiếm đơn thực hiện cùng lượng công việc bằng một vòng lặp và có ít trường hợp biên hơn.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def searchMatrix(matrix, target):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Đối số
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
Đầu ra mong đợi
true