Röportaj soru - sıralanmış dizide Arama X X bu dizin[i] = i

SORU

13 Kasım 2010, CUMARTESİ

Röportaj soru - sıralanmış dizide Arama X X bu dizin[i] = i

Benim röportajda şu soru dün soruldu:

Bir düşünün Java veya C dizi deyip sıralanmış X ve hiçbir iki öğe aynı. Nasıl iyi bir dizin bul söylersin i o dizinde bir öğe de i gibi. X[i] = i.

Açıklama olarak o da bana bir örnek verdi:

      Array X : -3 -1 0 3 5 7 
      index   :  0  1 2 3 4 5

      Answer is 3 as X[3] = 3.

Aklıma gelen en iyi doğrusal bir arama oldu. Görüşmeden sonra ben bu sorunu çok gerçi ama daha iyi bir çözüm bulamadı. Benim iddiam şudur: gerekli özellik ile eleman dizi. içinde herhangi bir yerde olabilir Ayrıca her eleman kontrol etmemiz gerekiyor o yüzden dizinin sonunda olabilir.

Ben sadece haklı olduğumu topluluk burada teyit etmek istiyorum. Haklı olduğumu bana:) söyle lütfen

Teşekkürler

CEVAP

13 Kasım 2010, CUMARTESİ

Bu biraz değiştirilmiş binary search kullanarak O(logN) O(1) uzayda yapılabilir.

Y[i] = X[i] - i Bu yeni bir dizi Y düşünün

Array X : -3 -1   0  3  5  7
index   :  0  1   2  3  4  5
Array Y : -3 -2  -2  0  1  2

X element beri vardırartıyorsipariş, öğeleri yeni dizi Y olacaknon-azalansipariş. Bu yüzden birikili aramaY 15 *cevap verecektir.

Ama Y oluşturma O(N) alan ve O(N) zaman alacaktır. Yani yerine yeni dizi oluşturma sadece bir tür ikili arama değiştir 20* *referans X[i] - i ile değiştirilir.

Algoritma:

function (array X) 
       low  = 0
       high = (num of elements in X) - 1

       while(low <= high) 
               mid = (low   high) / 2

               // change X[mid] to X[mid] - mid
               if(X[mid] - mid == 0)
                       return mid

               // change here too
               else if(X[mid] - mid < 0)
                       low = mid   1;

               else
                       high = mid - 1;
       end while

       return -1 // no such index exists...return an invalid index.

end function

Java implementation

C implementation

Bunu Paylaş: