Search a 2D Matrix

Q: 2B Matris Arama işleminin zaman karmaşıklığı nedir?

Düzleştirilmiş ızgara üzerinde ikili arama, O(log(m × n)) zamanda ve O(1) alanda çalışır: 10000 hücre için en fazla 14 karşılaştırma. log(m × n) = log m + log n olduğundan, önce satırı, ardından satırın içini aramayla aynı sonucu verir.

Q: Sağ üst köşeden ilerleme yöntemini mi yoksa ikili aramayı mı kullanmalısınız?

Köşe yürüyüşü O(m + n) adım sürer ve yalnızca satırların ve sütunların sıralı olmasını gerektirir; bu nedenle bir satırın, üstündeki satırın bittiği yerin altında başlayabileceği varyantı da çözer. Buradaki gibi her satır bir öncekinin bittiği yerin üstünde başladığında ikili arama daha hızlıdır.

Q: Satır için bir, satırın içinde bir tane olmak üzere iki ikili arama yapmak da doğru mudur?

Evet. İlk sütunda, ilk değeri target değerinden küçük veya eşit olan son satırı ikili aramayla bul, ardından o satırda ikili arama yap. O(log m + log n) süresinde çalışır; karmaşıklık sınırı aynıdır. Tek arama, bir döngüyle ve daha az uç durumla aynı işi yapar.

Ortaİkili arama

+10

Size m satır ve n sütun olan bir tamsayı ızgarası matrix ve bir tamsayı target veriliyor. Her satır artan sırada sıralıdır ve her satırın ilk değeri, üstündeki satırın son değerinden büyüktür. target ızgarada görünüyorsa true, aksi takdirde false döndürün; bunu O(log(m × n)) zamanda yapın.

Fonksiyon

searchMatrix(matrix: integer-2d-array, target: integer) → boolean

matrixinteger-2d-array: satırların listesi olarak verilen ve satır satır sıralanan ızgara
targetinteger: aranacak değer
Döndürürboolean: hedef ızgaradaysa doğru, aksi takdirde yanlış

Kısıtlar

1 ≤ m, n ≤ 100, burada m = matrix.length ve n = matrix[i].length
Her satırın uzunluğu n ile aynıdır.
-10⁴ ≤ matrix[i][j], target ≤ 10⁴
Her satır kesin olarak artan sırada sıralanmıştır ve her satırın ilk değeri, önceki satırın son değerinden büyüktür.

Örnekler

Girdi: matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
Çıktı: true
Açıklama: Satır satır okunduğunda, 12 değer sıralı tek bir listedir. 0 ile 11 arasındaki konumlarda yapılan ikili arama, 5. konumda 21'i kontrol eder (çok küçük), 8. konumda 33'ü kontrol eder (çok büyük), ardından 6. konumda 26'yı bulur.

Ek soru

Satırların uzunlukları farklı olsaydı, ancak yine de baştan sona sıralı olsalardı, bir konumu satır ve sütuna nasıl dönüştürürdün ve aramanın maliyeti ne olurdu?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

İki sıralama kuralı birlikte, satır satır okunduğunda ızgarayı m × n değerden oluşan sıralı bir liste hâline getirir. Bu listede konuma göre ikili arama yapın ve tek bir bölme işlemiyle her konumu yeniden bir satır ve sütuna dönüştürün. Böylece 100'e 100'lük bir ızgarada 10000 yerine en fazla 14 karşılaştırma gerekir.

Her hücreyi kontrol et

Sezgi

Her hücreyi target ile karşılaştır ve eşleşme olduğunda true, son hücreden sonra false döndür. Her hücreyi okuduğu için sıralı olsun ya da olmasın her ızgarada doğrudur. Sıralamadan hiç yararlanmaz; bu yüzden 100'e 100'lük bir ızgara en fazla 10000 karşılaştırma gerektirir.

Algoritma

matrix içindeki her satır için, her değere sırayla bak.
Değer target değerine eşitse true döndür.
Döngülerden sonra false döndür.

def searchMatrix(matrix, target):
    for row in matrix:
        for value in row:
            if value == target:
                return True
    return False

Sağ üst köşeden yürü

Sezgi

Sağ üstteki hücreden sola doğru her değer daha küçüktür ve aşağı doğru her değer daha büyüktür. Hücre target değerinden büyükse, altındaki sütun da daha büyüktür: sola ilerleyip o sütunu ele. Daha küçükse, solundaki satır da daha küçüktür: aşağı ilerleyip o satırı ele.

İlk örnekte 14, 26'dan küçüktür; bu yüzden aşağı inip 30'a gel. 30 daha büyüktür; bu yüzden sola ilerleyip eşleşme olan 26'ya gel. Her adım bir satırı veya sütunu eler, dolayısıyla en fazla m + n adım atarsın: 100'e 100'lük bir ızgarada 200 adım. Bu yöntem için yalnızca satırların ve sütunların sıralı olması gerekir; dolayısıyla bu ızgaranın sunduğu bilgilerin yarısını kullanmaz.

Algoritma

0 satırından ve son sütundan başlayın.
Satır ve sütun ızgaranın içinde olduğu sürece hücreyi okuyun.
target değerine eşitse true döndürün.
Daha büyükse bir sütun sola gidin; daha küçükse bir satır aşağı gidin.
Izgaranın dışına çıktığınızda false döndürün.

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 False

Yassılaştırılmış ızgarada ikili arama

Sezgi

Hücreleri satır satır numaralandır: 0. satır, 0 ile n - 1 arasındaki konumları; 1. satır n ile 2n - 1 arasındaki konumları tutar ve bu böyle devam eder. Her satır sıralıdır ve önceki satırın bittiği yerin üstünden başlar, bu yüzden değerler konumla birlikte yalnızca artar. Bu, sıralı bir listedir ve ikili arama uygulanabilir.

Listeyi hiçbir zaman oluşturmazsın. Tam sayı bölmesiyle, p konumu p / n satırında ve p % n sütunundadır. İlk örnekte n = 4, dolayısıyla 6. konum 1. satırda, 2. sütundadır ve burada 26 bulunur. Her karşılaştırma, target değerini tutabilecek konumların sayısını yarıya indirir: 10000 hücre için en fazla 14 karşılaştırma ve ek bellek olarak iki indeks gerekir.

Algoritma

m ve n satır ve sütun sayıları olsun ve lo = 0, hi = m × n - 1 olarak ayarlayın.
lo ≤ hi olduğu sürece, mid değerini ikisinin tam ortasına alın.
value = matrix[mid / n][mid % n] değerini okuyun.
value, target değerine eşitse true döndürün. Daha küçükse lo = mid + 1 olarak ayarlayın; aksi hâlde hi = mid - 1 olarak ayarlayın.
Döngü sona erdiğinde false döndürün.

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

Tuzaklar ve uç durumlar

Sütunlar yerine satır sayısına bölmek. p konumu p / n satırındadır; yerine m kullanıldığında kod kare ızgaralarda çalışır, ancak 3 satır ve 4 sütunda başarısız olur.
İki aramalı sürümde, target değerinin matrix[0][0] değerinden küçük olma durumunu ele almamak. Hiçbir satır bu değerde veya daha aşağıda başlamaz ve -1 satır indeksi ikinci aramaya ulaşır.
Kapsayıcı bir hi değeriyle lo < hi koşuluna göre döngüye girmek. target değerini içeren 1'e 1'lik bir ızgara false döndürür, çünkü döngü hiç çalışmaz.
Lua ve R'de, 1 tabanlı indekslere geçişi unutmak: p konumu p / n + 1 satırında, p % n + 1 sütunundadır.

Sıkça sorulan sorular3

2B Matris Arama işleminin zaman karmaşıklığı nedir?

Düzleştirilmiş ızgara üzerinde ikili arama, O(log(m × n)) zamanda ve O(1) alanda çalışır: 10000 hücre için en fazla 14 karşılaştırma. log(m × n) = log m + log n olduğundan, önce satırı, ardından satırın içini aramayla aynı sonucu verir.

Sağ üst köşeden ilerleme yöntemini mi yoksa ikili aramayı mı kullanmalısınız?

Köşe yürüyüşü O(m + n) adım sürer ve yalnızca satırların ve sütunların sıralı olmasını gerektirir; bu nedenle bir satırın, üstündeki satırın bittiği yerin altında başlayabileceği varyantı da çözer. Buradaki gibi her satır bir öncekinin bittiği yerin üstünde başladığında ikili arama daha hızlıdır.

Satır için bir, satırın içinde bir tane olmak üzere iki ikili arama yapmak da doğru mudur?

Evet. İlk sütunda, ilk değeri target değerinden küçük veya eşit olan son satırı ikili aramayla bul, ardından o satırda ikili arama yap. O(log m + log n) süresinde çalışır; karmaşıklık sınırı aynıdır. Tek arama, bir döngüyle ve daha az uç durumla aynı işi yapar.

def searchMatrix(matrix, target):
    # Kodu buraya yazın

Test #1

Test #2

Argümanlar

matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]
target = 26

Beklenen Çıktı

true

Search a 2D Matrix

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her hücreyi kontrol et

Sağ üst köşeden yürü

Yassılaştırılmış ızgarada ikili arama

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler