Son Java bir telefon röportajında bu soruyu sordu:

Aşağıdaki özelliklere sahip (0-1) NxN ikili bir matris verilmiştir:

• Her satır sıralanmış (0 . sıra 1. sıra) izledi
• Her satır işaretsiz bir tamsayı (bit okuma) temsil eder
• Her satır benzersiz

Örnek:

0 1 1
1 1 1
0 0 1

Bit satır sıralanır ve sıra tam sayılar 3, 7 ve 1 temsil her değerleri.

Satırın en küçük tamsayı temsil eden bulun. Yukarıdaki örnekte, cevap 1 tam sayısını temsil eden 3, satır.

İkinci dereceden bir karmaşıklık kaba kuvvet ile başladı. Görüşmeci sıralama özelliği istismar olduğumu söyleyerek cevap verdi.

Çok düşündükten sonra, her satır üzerinde ikili arama kullandım ve O(nlogn) geldi. Eğer herhangi bir daha fazla geliştirmek misin diye sordu. Çok düşündüm ama geliştirmek için başarısız oldu.

Eğer herkes imporoving üzerinde herhangi bir işaretçiler verebilir eğer çok memnun olurum.

Başka bir örnek:

0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1

Cevap tam sayı 0 temsil eden 3, satır olacaktır.

Satır 1 ile başlar. 8 ** ilk girene kadar. Git 2, ama aynı sütun içinde kalır ve satır 1 bir vurmak kadar doğru gitmiyor işlemi tekrarlayın. Bunu tekrar tekrar yapın. İçinde son sağ çıktı satır cevap.

Bu(N M) Ç çözüm (soru verilen bir NxN Kare matris veya O(N) bu yüzden olmak üzere matris).

Örnek kullanımı:

0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1

.'In burada yol ikiye bölünen temsil eder:

. . 1 1
0 . . .
0 0 0 . . Last right step, therefore this is our answer
1 1 1 1 .

Bu çözümü olmayan bir kare matrisleri, en kötü durum O(N M) istinat verimliliği bu yüzden olmak üzere bir matris için çalışıyor.

Neden bu işe yarıyor mu? Numaraları sıralama olacağı garanti her satır 0. 1 Serisi ardından bir dizi olacak demektir. Bir satırın büyüklüğü ne kadar bir 1 isabet önce gidebilirsiniz eşdeğerdir. Eğer bir satır seni bir daha sadece izleyerek alabilir eğer 0, daha önce denedik bir şey daha uzun olmalı.

Kod Python:

li = [[0, 1, 1, 1],
      [0, 0, 0, 1],
      [0, 0, 0, 0],
      [1, 1, 1, 1]]

ans, j = 0, 0
for i, row in enumerate(li):
  while j < len(row) and row[j] == 0:
    j  = 1
    ans = i

print "Row", ans 1, "".join(map(str, li[ans]))

Ayrıca daha basit bir çözüm, her zaman NxN Kare matris ve ayrı bir satır bir araya getirdiğin kısıtlamalar nedeniyle vardır. Birlikte en düşük değer içeren satırları ya 0 0 ... 0 1 0 0 ... 0 0 olacak demek. Çünkü bu N-N 1 Olası numaraları temsil edilen matris, yani "eksik" ya da çok sayıda 0 (bu durumda en küçük değer gösterilir 1) veya başka bir şey (en küçük değeri 0'dır).

Bu bilgi ile, bir 0 için sağdan ikinci kontrol edin. Tek bulduğumuz zaman, onun doğru görüyoruz ve bu bizim cevabımız var başka bir 0 varsa (sadece 0 ile biten bir satır da olabilir). Aksi takdirde, başka bir 0 sütun için araştırmaya devam ediyoruz. Bulamazsak başka bir 0, ne bulundu satırı arıyoruz (orada sadece bir satır sonu 01 ve o zamandan beri orada hiç bitmeyen 00, Bu en küçüğüdür).

Kod Python:

li = [[0, 1, 1, 1],
      [0, 0, 0, 1],
      [0, 0, 0, 0],
      [1, 1, 1, 1]]

for i, row in enumerate(li):
  if row[-2] == 0:
    ans = i
    if row[-1] == 0:
      break

print "Row", ans 1, "".join(map(str, li[ans]))

Çözüm soru cevaplar ile az zorluk O(N), ama genelleme tanıtıcı için kare olmayan matrislerin bu yüzden olmak üzere olan ya da olmayan farklı numaralar yapar onun kötü durum verimliliği O(N^2). Ben şahsen ilk çözüm tercih ederim.