Search a 2D Matrix
Kamu mendapatkan grid bilangan bulat matrix dengan m baris dan n kolom, serta bilangan bulat target. Setiap baris diurutkan dari nilai terkecil ke terbesar, dan nilai pertama setiap baris lebih besar daripada nilai terakhir baris di atasnya. Kembalikan true jika target muncul di grid dan false jika tidak, dalam waktu O(log(m × n)).
Fungsi
- matrixinteger-2d-array
- kisi, yang diberikan sebagai list baris, diurutkan baris demi baris
- targetinteger
- nilai yang dicari
- Mengembalikanboolean
- true jika target berada di grid, false jika tidak
Batasan
1 ≤ m, n ≤ 100, denganm = matrix.lengthdann = matrix[i].length- Setiap baris memiliki panjang yang sama, yaitu
n. -104 ≤ matrix[i][j], target ≤ 104- Setiap baris diurutkan secara menaik ketat, dan nilai pertama setiap baris lebih besar daripada nilai terakhir baris sebelumnya.
Contoh
- Input
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- Output
- true
- Penjelasan
- Baca baris demi baris, 12 nilai tersebut membentuk satu list terurut. Pencarian biner pada posisi 0 hingga 11 memeriksa 21 di posisi 5 (terlalu kecil), 33 di posisi 8 (terlalu besar), lalu menemukan 26 di posisi 6.
- Input
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- Output
- false
- Penjelasan
- 16 akan muncul setelah 14, nilai terakhir pada baris 0, dan sebelum 17, nilai pertama pada baris 1. Tidak ada apa pun di antara keduanya, jadi 16 tidak ada di dalam grid.
Pertanyaan lanjutan
Misalkan baris-barisnya memiliki panjang yang berbeda, tetapi tetap terurut dari awal hingga akhir. Bagaimana kamu mengubah posisi menjadi baris dan kolom, dan berapa biaya pencariannya?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Baca matriks baris demi baris, dari kiri ke kanan, seolah-olah matriks itu adalah satu list panjang. Apa yang kamu perhatikan tentang urutan nilai dalam list itu?
Kedua aturan tersebut berarti seluruh matriks, dibaca baris demi baris, merupakan satu list
m × nyang terurut. Kamu dapat melakukan pencarian biner tanpa perlu membuat list tersebut.Pencarian biner pada posisi
0hinggam × n - 1. Posisipberada di barisp / ndan kolomp % n(pembagian bilangan bulat), sehingga setiap langkah membaca satu sel dan membuang setengah dari posisi yang tersisa.
Solusi
Gabungan kedua aturan pengurutan tersebut membuat grid, jika dibaca baris demi baris, menjadi satu list nilai m × n yang terurut. Lakukan pencarian biner pada list itu berdasarkan posisi, lalu ubah setiap posisi kembali menjadi baris dan kolom dengan satu pembagian. Grid berukuran 100 kali 100 hanya memerlukan paling banyak 14 perbandingan, bukan 10000.
Periksa setiap sel
Intuisi
Bandingkan setiap sel dengan target dan kembalikan true jika cocok, false setelah sel terakhir. Cara ini membaca setiap sel, jadi benar untuk grid apa pun, baik terurut maupun tidak. Cara ini tidak pernah menggunakan urutannya, jadi grid berukuran 100 kali 100 memerlukan hingga 10000 perbandingan.
Algoritma
- Untuk setiap baris dalam
matrix, periksa setiap nilai secara berurutan. - Jika nilainya sama dengan
target, kembalikantrue. - Setelah perulangan, kembalikan
false.
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return FalseBerjalan dari sudut kanan atas
Intuisi
Dari sel kanan atas, setiap nilai di sebelah kiri lebih kecil dan setiap nilai di bawah lebih besar. Jika nilai sel lebih besar daripada target, kolom di bawahnya juga lebih besar: geser ke kiri dan singkirkan kolom itu. Jika nilainya lebih kecil, baris di sebelah kirinya juga lebih kecil: turun dan singkirkan baris itu.
Dalam contoh pertama, 14 lebih kecil daripada 26, jadi turun ke 30. 30 lebih besar, jadi geser ke kiri ke 26, yang cocok. Setiap langkah menghapus satu baris atau satu kolom, jadi kamu mengambil paling banyak m + n langkah: 200 langkah untuk grid 100 × 100. Pergerakan ini hanya memerlukan baris dan kolom yang terurut, jadi tidak memanfaatkan separuh informasi yang tersedia dalam grid ini.
Algoritma
- Mulai dari baris
0dan kolom terakhir. - Selama baris dan kolom masih berada di dalam grid, baca selnya.
- Jika nilainya sama dengan
target, kembalikantrue. - Jika nilainya lebih besar, geser satu kolom ke kiri; jika lebih kecil, geser satu baris ke bawah.
- Saat keluar dari grid, kembalikan
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 FalsePencarian biner pada grid yang diratakan
Intuisi
Beri nomor pada sel baris demi baris: baris 0 menampung posisi 0 hingga n - 1, baris 1 menampung n hingga 2n - 1, dan seterusnya. Setiap baris terurut dan dimulai setelah posisi akhir baris sebelumnya, jadi nilainya hanya meningkat seiring posisi. Itu adalah list terurut, dan pencarian biner dapat digunakan.
Kamu tidak perlu membuat list tersebut. Posisi p berada di baris p / n dan kolom p % n, dengan pembagian bilangan bulat. Pada contoh pertama, n = 4, jadi posisi 6 berada di baris 1, kolom 2, yang berisi 26. Setiap perbandingan membagi dua posisi yang mungkin berisi target: paling banyak 14 perbandingan untuk 10000 sel, dengan dua indeks sebagai memori tambahan.
Algoritma
- Misalkan
mdannadalah jumlah baris dan kolom, lalu tetapkanlo = 0,hi = m × n - 1. - Selama
lo ≤ hi, ambilmiddi titik tengah antara keduanya. - Baca
value = matrix[mid / n][mid % n]. - Jika
valuesama dengantarget, kembalikantrue. Jika nilainya lebih kecil, tetapkanlo = mid + 1; jika tidak, tetapkanhi = mid - 1. - Setelah perulangan berakhir, kembalikan
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
Jebakan dan kasus tepi
- Membagi dengan jumlah baris, bukan kolom. Posisi
pberada di barisp / n; jika diganti denganm, kode berhasil pada grid persegi dan gagal pada grid dengan 3 baris dan 4 kolom. - Pada versi dengan dua pencarian, tidak menangani
targetyang lebih kecil darimatrix[0][0]. Tidak ada baris yang dimulai pada atau di atas nilai tersebut, dan indeks baris-1mencapai pencarian kedua. - Melakukan perulangan dengan
lo < hisaathibersifat inklusif. Grid 1 kali 1 yang berisitargetmenghasilkanfalse, karena perulangan tidak pernah berjalan. - Dalam Lua dan R, lupa menggeser indeks agar dimulai dari 1: posisi
pberada di barisp / n + 1, kolomp % n + 1.
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu untuk mencari dalam matriks 2D?
Pencarian biner pada grid yang diratakan berjalan dalam waktu O(log(m × n)) dan ruang O(1): paling banyak 14 perbandingan untuk 10000 sel. Karena log(m × n) = log m + log n, kompleksitasnya sama dengan mencari baris, lalu mencari di dalamnya.
Haruskah kamu menggunakan penelusuran dari sudut kanan atas atau pencarian biner?
Penelusuran sudut membutuhkan O(m + n) langkah dan hanya memerlukan baris serta kolom yang terurut, sehingga cara ini juga menyelesaikan varian ketika sebuah baris dapat dimulai di bawah akhir baris di atasnya. Jika setiap baris dimulai di atas akhir baris sebelumnya, seperti di sini, pencarian biner lebih cepat.
Apakah dua pencarian biner, satu untuk baris dan satu lagi di dalamnya, juga benar?
Ya. Lakukan pencarian biner pada kolom pertama untuk mencari baris terakhir yang nilai pertamanya paling besar target, lalu lakukan pencarian biner pada baris tersebut. Operasi ini berjalan dalam O(log m + log n), dengan batas yang sama. Pencarian tunggal melakukan pekerjaan yang sama dengan satu perulangan dan lebih sedikit kasus khusus.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def searchMatrix(matrix, target):
# Tulis kodemu di siniTes #1
Tes #2
Argumen
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
Output yang diharapkan
true