Find Minimum in Rotated Sorted Array

Q: Döndürülmüş sıralı bir dizide minimum değeri bulmanın zaman karmaşıklığı nedir?

İkili aramayla O(log n) zaman ve O(1) ek alan. Her adım aralığın bir yarısını tutar; bu nedenle 5000 öğeli bir liste en fazla 13 karşılaştırma gerektirir. Düşüşü taramak O(n) zaman alır: minimum sondaysa her öğeyi okur.

Q: Neden nums[mid] değerini nums[lo] ile değil de nums[hi] ile karşılaştırıyoruz?

Çünkü nums[hi] minimumun hangi tarafta olduğunu her zaman belirler, nums[lo] ise belirlemez. nums[mid] > nums[hi] ise değerler mid ile hi arasında olmalıdır; aksi takdirde nums[mid..hi] yükselir ve minimum mid konumunda veya ondan önce bulunur. nums[lo] için nums[mid] > nums[lo] sonucu hem minimumun nums[lo] olduğu döndürülmemiş bir listeyle hem de minimumun mid konumunun sağında bulunduğu döndürülmüş bir listeyle uyumludur.

Q: Sıralanmış bir dizinin kaç kez döndürüldüğünü nasıl bulursunuz?

Aynı ikili aramayı çalıştırın ve nums[lo] yerine minimumun indeksi olan lo değerini döndürün. Döndürmeyi son öğeyi başa taşımak olarak sayarsanız, bu indeks döndürme sayısıdır. Bu problemde olduğu gibi, ilk öğeyi sona taşımak olarak sayarsanız, sayı (n - lo) mod n olur: [11, 13, 15, 17, 2, 5, 9] dizisinde minimum 4. indekstedir ve 7 eksi 4, taşınan 3 değeri verir.

Q: Dizide yinelenen değerler olduğunda ikili arama çalışır mı?

Değişmeden değil. [2, 2, 2, 0, 2] içinde nums[mid] , nums[hi] değerine eşit olabilir; bu durumda da iki taraftan hiçbiri elenemez. Bu durumda hi = hi - 1 ile aralığı daraltmak güvenlidir; çünkü nums[hi] değerinin bir kopyası mid konumunda aralıkta kalır. Ancak eşit değerlerden oluşan ve aralarında gizlenmiş daha küçük bir değer bulunan bir liste için bu işlem O(n) maliyetlidir.

Ortaİkili arama

+10

Birbirinden farklı tamsayılardan oluşan bir liste artan sırada sıralandı ve ardından döndürüldü: sıfır olabilir, belirli sayıda öğe baştan alınıp aynı sırayla sona taşındı. Örneğin, [2, 5, 9, 11, 13, 15, 17] 3 kez döndürüldüğünde [11, 13, 15, 17, 2, 5, 9] olur. Döndürülmüş nums listesini alıyorsun. En küçük değerini O(log n) zamanda döndür.

Fonksiyon

findMin(nums: integer-array) → integer

numsinteger-array: döndürülmüş sıralı farklı tam sayılar listesi
Döndürürinteger: nums içindeki en küçük değer

Kısıtlar

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
nums içindeki tüm değerler birbirinden farklıdır.
nums, bir k değeri kadar döndürülmüş artan bir listedir; 0 ≤ k < nums.length; k = 0 listeyi döndürülmemiş bırakır.

Örnekler

Girdi: nums = [11, 13, 15, 17, 2, 5, 9]
Çıktı: 2
Açıklama: Değerler 11'den 17'ye yükselir, ardından 2'ye düşer; ikinci çalışma burada başlar. Arama, 3. indekste 17 > 9 olduğunu görür, dolayısıyla minimum sağındadır; ardından 5 ≤ 9 ve 2 ≤ 5, aralık yalnızca 2'yi içeren 4. indeks olana kadar hi'yi geri çeker.

Girdi: nums = [4, 7, 10, 12]
Çıktı: 4
Açıklama: Bu liste 0 kadar döndürüldü, dolayısıyla hâlâ sıralıdır ve en küçük değer ilk elemanıdır. Her orta değer son değerden küçük veya ona eşittir, bu yüzden hi sola doğru ilerlemeye devam eder ve 4 değerini içeren 0 indeksine ulaşır.

Girdi: nums = [30, -6, 0, 8, 19]
Çıktı: -6
Açıklama: Ön taraftan arka tarafa dört değer taşındı; böylece en büyük değer olan 30 artık ilk sırada, en küçük değer olan -6 ise 1. indekste yer alıyor. Arama, aralığı 0 ve 1. indekslere daraltıyor, 30 > -6 olduğunu görüyor ve lo değerini 1'e taşıyor.

Ek soru

nums içindeki k'ıncı en küçük değeri sıralamadan O(log n) sürede döndürebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Döndürülmüş sıralı bir liste, artan iki diziden oluşur: [11, 13, 15, 17] ve ardından [2, 5, 9]. En küçük değer, değerlerin azaldığı tek yerin hemen sonrasında, ikinci dizinin ilk değeridir. Listeyi baştan sona taramak bu düşüşü O(n) sürede bulur. Ortadaki bir değeri aralığın son değeriyle karşılaştırmak, ortadaki değerin düşüşün hangi tarafında olduğunu gösterir; böylece ikili arama düşüşü O(log n) sürede bulur.

Değerler düşene kadar yürü

Sezgi

Sıralı bir listede her değer kendisinden önceki değerden büyüktür. Listeyi döndürmek, her iki sıralı diziyi de sıralı tutar ve bunun bozulduğu tam olarak tek bir yer oluşturur: en büyük değerin ardından en küçüğü gelir. Bu yüzden soldan sağa ilerleyin ve solundaki komşusundan küçük olan ilk değeri döndürün. Böyle bir değer yoksa liste 0 kez döndürülmüştür ve minimum değer nums[0] olur.

[11, 13, 15, 17, 2, 5, 9] listesinde ilerleme 13, 15 ve 17'yi geçer; bunların her biri kendisinden önceki değerden büyüktür. Ardından 2'nin 17'den küçük olduğu 4. indiste durur. Bu, her değerin minimumunu bulmaktan zaten daha iyidir; çünkü düşüşe ulaştığında durur. Ancak düşüş herhangi bir yerde olabilir. Döndürme tek bir öğeyi yerinden oynattığında (örneğin [2, 3, 4, 5, 6, 7, 8, 1]), ilerleme listenin tamamını okur: 5000 öğe için 5000 karşılaştırma gerekirken ikili arama 13 karşılaştırma gerektirir.

Algoritma

1'den n-1'e kadar her i indeksi için nums[i] ile nums[i-1] değerlerini karşılaştırın.
nums[i] < nums[i-1] ise nums[i] değerini döndürün: ikinci dizi burada başlar.
Döngü sona ererse liste döndürülmemiştir: nums[0] değerini döndürün.

def findMin(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            return nums[i]  # the only drop: the second run starts here
    return nums[0]  # no drop: the list was not rotated

Son değere göre ikili arama

Sezgi

Şu vaadi koru: minimum değer, uç noktalar da dahil olmak üzere lo ile hi arasındadır. Başlangıçta bu aralık listenin tamamıdır. Ortadaki değere bak ve bunu aralığın son değeri olan nums[hi] ile karşılaştır.

nums[mid] > nums[hi] ise değerler mid ile hi arasında bir yerde düşer ve minimum değer bu düşüşün hemen sonrasındaki değerdir; yani mid değerinin sağındadır: lo = mid + 1 yap. Aksi hâlde nums[mid] < nums[hi] (değerler birbirinden farklıdır), dolayısıyla nums[mid..hi] aralığındaki değerler herhangi bir düşüş olmadan artar. O hâlde minimum değer nums[mid] ya da ondan önceki bir değerdir; bu yüzden hi = mid yap. mid değerini atlayıp geçme: minimum değer o olabilir. Her iki hamle de bu vaadi koruyup aralığı daraltır ve lo, hi değerine ulaştığında geriye kalan tek değer minimumdur.

İlk örneği adım adım izleyelim: [11, 13, 15, 17, 2, 5, 9]. 0 ile 6 arasındaki aralığın orta noktası 3, bu noktadaki değer 17'dir ve nums[6] = 9 değerinden büyüktür; bu yüzden lo 4 olur. 4 ile 6 arasındaki aralığın orta noktası 5, bu noktadaki değer 5'tir ve 9'dan büyük değildir; bu yüzden hi 5 olur. 4 ile 5 arasındaki aralığın orta noktası 4, bu noktadaki değer 2'dir ve 5'ten büyük değildir; bu yüzden hi 4 olur. nums[4] = 2 değerini döndür.

Her adımda aralık yarıya iner; bu yüzden döngü en fazla yaklaşık log2(n) kez çalışır: 5000 eleman için 13 adım ve ek bellek olarak iki indeks.

Algoritma

lo = 0 ve hi = n-1 olarak ayarla.
lo < hi olduğu sürece mid = lo + (hi - lo) / 2 değerini hesapla.
nums[mid] > nums[hi] ise lo = mid + 1 olarak ayarla.
Aksi takdirde hi = mid olarak ayarla.
Döngü sona erdiğinde nums[lo] değerini döndür.

def findMin(nums):
    lo, hi = 0, len(nums) - 1  # the minimum sits in nums[lo..hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the values drop after mid, so the minimum is right of it
        else:
            hi = mid      # nums[mid..hi] climbs: the minimum is at mid or left of it
    return nums[lo]

Tuzaklar ve uç durumlar

Döngü dört satır uzunluğundadır ve her satırda cazip ama yanlış bir sürüm vardır.

İkinci dalda hi = mid - 1 yazmak. Bu dal, mid minimumun kendisi olabileceğinde çalışır. [3, 1, 2] içinde ortadaki 1 değeri 2’den büyük değildir; bu yüzden hi 0’a düşer ve fonksiyon 3 döndürür.
lo ≤ hi koşuluyla döngüye girmek. lo, hi değerine eşitlendiğinde mid her ikisine de eşit olur, nums[mid] > nums[hi] false olur ve hi = mid hiçbir şeyi değiştirmez: döngü hiç bitmez. Aralıkta tek eleman kaldığında durmak için lo < hi kullanın.
nums[hi] yerine nums[lo] ile karşılaştırmak. Döndürülmemiş [1, 2, 3, 4, 5] listesinde ortadaki 3 değeri nums[0] = 1 değerinden büyüktür; bu da düşüşün sağ tarafta olduğu izlenimini verir. Böylece arama, 0. indeksteki gerçek minimumdan uzaklaşır ve 4 döndürür.
nums[lo] yerine lo döndürmek. İstenen değer; indeks ise farklı bir sorunun yanıtıdır (döndürme sayısıyla ilgili SSS’ye bakın).
Listenin döndürülmüş olduğunu varsaymak. 0 kadar döndürmeye izin verilir ve düşüşü yedek bir durum olmadan arayan kod, listenin sonunun ötesini okur veya hiçbir şey döndürmez. Hiç düşüş yoksa nums[0] döndürün.

Sıkça sorulan sorular4

Döndürülmüş sıralı bir dizide minimum değeri bulmanın zaman karmaşıklığı nedir?

İkili aramayla O(log n) zaman ve O(1) ek alan. Her adım aralığın bir yarısını tutar; bu nedenle 5000 öğeli bir liste en fazla 13 karşılaştırma gerektirir. Düşüşü taramak O(n) zaman alır: minimum sondaysa her öğeyi okur.

Neden nums[mid] değerini nums[lo] ile değil de nums[hi] ile karşılaştırıyoruz?

Çünkü nums[hi] minimumun hangi tarafta olduğunu her zaman belirler, nums[lo] ise belirlemez. nums[mid] > nums[hi] ise değerler mid ile hi arasında olmalıdır; aksi takdirde nums[mid..hi] yükselir ve minimum mid konumunda veya ondan önce bulunur. nums[lo] için nums[mid] > nums[lo] sonucu hem minimumun nums[lo] olduğu döndürülmemiş bir listeyle hem de minimumun mid konumunun sağında bulunduğu döndürülmüş bir listeyle uyumludur.

Sıralanmış bir dizinin kaç kez döndürüldüğünü nasıl bulursunuz?

Aynı ikili aramayı çalıştırın ve nums[lo] yerine minimumun indeksi olan lo değerini döndürün. Döndürmeyi son öğeyi başa taşımak olarak sayarsanız, bu indeks döndürme sayısıdır. Bu problemde olduğu gibi, ilk öğeyi sona taşımak olarak sayarsanız, sayı (n - lo) mod n olur: [11, 13, 15, 17, 2, 5, 9] dizisinde minimum 4. indekstedir ve 7 eksi 4, taşınan 3 değeri verir.

Dizide yinelenen değerler olduğunda ikili arama çalışır mı?

Değişmeden değil. [2, 2, 2, 0, 2] içinde nums[mid], nums[hi] değerine eşit olabilir; bu durumda da iki taraftan hiçbiri elenemez. Bu durumda hi = hi - 1 ile aralığı daraltmak güvenlidir; çünkü nums[hi] değerinin bir kopyası mid konumunda aralıkta kalır. Ancak eşit değerlerden oluşan ve aralarında gizlenmiş daha küçük bir değer bulunan bir liste için bu işlem O(n) maliyetlidir.

def findMin(nums):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

nums = [11, 13, 15, 17, 2, 5, 9]

Beklenen Çıktı