Về Chương 6
Dò Quét Lưới Kép

Dò Mìn Ma Trận (2D Binary Search)

Từ độ phức tạp O(M*N), giải thuật rẽ luồng giảm xuống rực rỡ chỉ còn O(M + N). Vứt bỏ từng hàng/cột qua 1 lượt Scan.

Truy Tìm:
14
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
Bắt đầu từ góc trên bên phải: Row 0, Col 4. Giá trị hiện tại là [15].
Tốc Độ
Thống Kê
Tọa Độ (R, C)
(0, 4)
Ô Hiện Tại
15
Tiến Độ

🗺️ Nhị Phân Góc Chéo

Đây là bài toán cực kỳ kinh điển của Leetcode (Search a 2D Matrix II). Mọi Hàng (Row) được sort Trái-Phải, mọi Cột (Col) được sort Trên-Dưới.

Tư Duy Hủy Diệt Cột / Hàng

Bằng việc luôn khởi đầu tại tọa độ Top-Right (r=0, c=N-1), phần tử đó đang làm Chúa Tể của cái bóng lưng nó.

  • Nếu Value Khảo Sát > TARGET: Chắc chắn target phải VỀ BÊN TRÁI. Gạch Cột! `c--`
  • Nếu Value Khảo Sát < TARGET: Chắc chắn target phải XUỐNG DƯỚI. Gạch Hàng! `r++`