Check if an Array Is Sorted
Bir tamsayı dizisi nums veriliyor. Dizi azalmayan sıradaysa, yani her eleman kendisinden sonraki elemana eşit veya ondan küçükse true, aksi takdirde false döndürün. Eşit komşu elemanlar sorun değildir: [2, 2, 3] sıralı kabul edilir. Tek elemanlı bir dizi sıralıdır.
Fonksiyon
- numsinteger-array
- denetlenecek tam sayı dizisi
- Döndürürboolean
- her öğe kendisinden sonraki öğeden küçük veya ona eşit olduğunda true, aksi takdirde false
Kısıtlar
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Örnekler
- Girdi
- nums = [1, 3, 3, 7]
- Çıktı
- true
- Açıklama
- Her adım yükselir ya da aynı seviyede kalır: 1'den 3'e, 3'ten 3'e, 3'ten 7'ye. 3'ün tekrarlanmasına izin verilir, bu nedenle yanıt
trueolur.
- Girdi
- nums = [2, 5, 4, 9]
- Çıktı
- false
- Açıklama
- 5'ten 4'e geçiş aşağı doğru gider. Diziyi sıralanmamış hâle getirmek için böyle bir adım yeterlidir; sonunda bulunan 9 en büyük değer olsa bile cevap
falseolur.
Gönderirken +16 gizli test
Ek soru
Artan ya da azalan sırada olabilen bir diziyi tek geçişte nasıl kontrol edersiniz?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir dizi sıralı değilse, bunu dizinin neresinde görebilirsiniz? Birbirinden uzaktaki öğeleri karşılaştırmanız gerekir mi?
Her öğeyi hemen ardından gelenle karşılaştırmak yeterlidir. Eşit komşulara izin verilir; sıralamayı yalnızca bir düşüş bozar.
Komşu çiftler üzerinde döngü kur ve sol değerin sağ değerden büyük olduğu ilk çiftte
falsedöndür. Böyle bir çift yoksatruedöndür.
Çözüm
Bir dizi, hiçbir eleman kendisinden hemen sonra gelen elemandan büyük değilse sıralıdır. Birbirinden uzaktaki elemanları karşılaştırmana gerek yoktur: her komşu çift sıralıysa dizinin tamamı da sıralıdır. Böylece kontrol, ilk sıralama bozukluğunda durabilen, n-1 çift üzerinde tek geçişe dönüşür.
Bir kopyayı sıralayın ve karşılaştırın
Sezgi
Sıralı bir dizi, sıralama işleminin değiştirmeyeceği dizidir. Bu yüzden nums dizisinin bir kopyasını oluşturun, kopyayı sıralayın ve konum konum özgün diziyle eşleşip eşleşmediğini kontrol edin. Her konum eşleşiyorsa nums zaten sıralıydı.
[2, 5, 4, 9] için sıralanmış kopya [2, 4, 5, 9] olur. 1. konumda özgün dizide 5, kopyada ise 4 bulunur; dolayısıyla yanıt false olur. [1, 3, 3, 7] için kopya özgün diziyle aynıdır ve yanıt true olur.
Bu doğru bir yöntemdir, ancak sorunun istediğinden fazlasını yapar. Sıralama O(n log n) maliyetlidir; 5000 sayı için yaklaşık 6 × 10^4 karşılaştırma gerekir ve kopya O(n) bellek kullanır. Ayrıca, ilk çift bile sıralama dışındaysa tüm diziyi okumaya devam eder.
Algoritma
- Orijinalinin değişmeden kalması için
nums'u kopyala. - Kopyayı artan sayısal sırada sırala.
- Kopyayı
numsile konum konum karşılaştır. - Her konum eşleşiyorsa
true, aksi takdirdefalsedöndür.
def isSorted(nums):
# sorted returns a new list, so nums itself is left as it was.
return sorted(nums) == numsKomşu çiftlerinin her birini karşılaştırın
Sezgi
Dizinin sıralı olup olmadığını anlamak için sıralanmış hâline ihtiyacın yok. Bir dizi, ancak ve ancak her eleman hemen ardından gelen elemandan küçük veya ona eşitse azalmayan sıradadır. ≤ bağıntısı geçişli olduğundan (a ≤ b ve b ≤ c, a ≤ c sonucunu verir), n-1 komşu çifti kontrol etmek tüm konum çiftlerini kapsar.
i değerini 1'den n-1'e kadar ilerlet ve nums[i-1] ile nums[i] değerlerini karşılaştır. [2, 5, 4, 9] için (2, 5) çifti uygundur, ancak (5, 4) çifti azaldığından 9'a bakmadan hemen orada false döndürürsün. Eşit komşular geçer, çünkü yalnızca > başarısız olur.
Her çift bir kez karşılaştırılır; dolayısıyla zaman karmaşıklığı O(n)'dir ve ek bellek olarak yalnızca döngü indeksi gerekir: O(1). İki değeri çıkarmak yerine doğrudan karşılaştır: değerler 10^9'a kadar çıkabildiğinden, fark 32 bitlik bir tamsayıda taşmaya neden olabilir.
Algoritma
ideğerini 1'denn-1'e kadar döngüye sok.nums[i-1] > nums[i]isefalsedöndür.- Döngü biterse
truedöndür. Tek elemanlı bir dizi döngüyü atlar ve sıralıdır.
def isSorted(nums):
for i in range(1, len(nums)):
# One step down anywhere breaks the order.
if nums[i - 1] > nums[i]:
return False
return True
Tuzaklar ve uç durumlar
Döngü kısa olduğundan hatalar kenarlarda ve karşılaştırmada ortaya çıkar.
- Eşit komşuları hata saymak.
nums[i-1] >= nums[i]koşulunu sınamak,[1, 3, 3, 7]dizisini reddeder. Sıralamayı yalnızca kesin bir azalma (>) bozar. - Dizinin sonunu aşarak okumak.
nums[i]ilenums[i+1]değerlerini karşılaştıran ve0ilen-1arasında ilerleyen bir döngü, dizinin dışını okumamak için bir adım erken durmalıdır.i = 1değerinden başlayıpi-1ile karşılaştırmak bu sorunu önler. - Karşılaştırmak yerine çıkarma yapmak.
nums[i] - nums[i-1] >= 0aynı gibi görünür, ancak10^9 - (-10^9) = 2 × 10^9değeri 32 bitlik bir int türüne sığmaz ve negatif bir sayıya sarar; bu nedenle[-1000000000, 1000000000]dizisinin sıralı olmadığı bildirilir.x - yolarak yazılmış bir qsort karşılaştırıcısında da aynı taşma sorunu görülür. - Sayıları metin olarak sıralamak. JavaScript'te, karşılaştırma işlevi olmadan kullanılan
sort(),10değerini9değerinden önce koyar; bu nedenle sıralama ve karşılaştırma denetimi yanlış sonuçlar verir.
Sıkça sorulan sorular4
Dizinin sıralı olup olmadığını nasıl kontrol edersiniz?
Her öğeyi bir sonraki öğeyle karşılaştırın. Herhangi bir öğe sağındaki komşusundan büyükse dizi sıralı değildir ve durabilirsiniz; böyle bir öğe bulmadan sona ulaşırsanız dizi sıralıdır. Bu işlem O(n) zaman ve O(1) ek alan gerektirir.
Komşuları kontrol etmek neden yeterlidir?
Sıralama bağıntısı zincirlidir: a ≤ b ve b ≤ c ise a ≤ c. Dolayısıyla her ardışık ikili sıralıysa, konumların her ikilisi de sıralıdır. Tersine, sıralanmamış her dizide değerin azaldığı en az bir ardışık ikili vardır.
Eşit öğelerden oluşan bir dizi sıralı mıdır?
Azalmayan sırada, evet: [4, 4, 4] sıralıdır çünkü hiçbir öğe kendisinden sonraki öğeden büyük değildir. Bir problem bunun yerine kesin artan sıra istiyorsa, eşit komşuları da reddedecek şekilde testi değiştir.
Bir kopyayı sıralayıp orijinaliyle karşılaştırabilir miyim?
Evet, doğru yanıtı verir; ancak kopya için O(n log n) zaman ve O(n) ek bellek gerektirir. Komşu kontrolü daha hızlıdır, kopya gerektirmez ve geri kalanını okumadan ilk adımda dönebilir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def isSorted(nums):
# Kodu buraya yazınDurum 1
Durum 2
Girdi
nums = [1, 3, 3, 7]
Beklenen
true