Second Largest Number
Bir tamsayı listesi olan nums veriliyor. Listenin ikinci en büyük farklı değerini döndür: maksimumdan kesinlikle küçük olan en büyük değeri. Değerler tekrarlanabilir; bu nedenle [5, 5, 3] için yanıt 3 olur, 5 değil. Listede her zaman en az iki farklı değer bulunur.
Fonksiyon
- numsinteger-array
- en az iki farklı değer içeren tam sayılar listesi
- Döndürürinteger
- maksimumdan küçük olan en büyük değer
Kısıtlar
2 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numsen az iki farklı değer içerir.
Örnekler
- Girdi
- nums = [4, 9, 2, 7, 9]
- Çıktı
- 7
- Açıklama
- Maksimum değer
9. İki kez görünür, ancak maksimum değerin ikinci kopyası sayılmaz; bu nedenle yanıt, bir sonraki düşük değer olan7'dir.
- Girdi
- nums = [-5, -1, -8]
- Çıktı
- -5
- Açıklama
- En büyükten en küçüğe doğru değerler
-1,-5,-8şeklindedir. İkinci en büyük değer, negatif olmasına rağmen-5'tir.
- Girdi
- nums = [6, 6, 6, 3]
- Çıktı
- 3
- Açıklama
- Yalnızca iki farklı değer vardır:
6ve3.6kaç kez tekrarlanırsa tekrarlansın, ikinci en büyük değer3'tür.
Ek soru
Tek geçişte, üç değişken kullanarak ve sıralama yapmadan üçüncü en büyük farklı değeri döndürebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Maksimum değeri bulmak tek bir değişken gerektirir. Listeyi okurken ikinci bir değişken neyi hatırlamanı sağlar?
En büyük ve birbirinden farklı ikinci en büyük değeri takip edin. Yeni bir değer en büyüğü geçebilir, iki değerin arasına yerleşebilir ya da hiçbir şeyi değiştirmeyebilir.
Aşağıdaki her iki değişkeni de izin verilen herhangi bir değerle başlatın.
x > largestiselargestdeğeriniseconddeğişkenine kaydırın vexdeğerini saklayın. Aksi takdirde,xbu iki değer arasındaysaseconddeğişkeninde saklayın.
Çözüm
İki ayrıntı bunu en büyük değeri bulmaktan daha zor hâle getirir. En büyük değer birden fazla kez görünebilir ve tekrar eden bir değer ikinci en büyük olarak bildirilmemelidir. Yanıt negatif olabilir; bu nedenle 0 ile başlayan bir değişken, tüm değerleri negatif olan bir listede yanlış yanıt verir. Tek bir geçişte, katı karşılaştırmalar kullanarak birbirinden farklı en büyük iki değeri takip etmek her iki sorunu da çözer.
Maksimum değeri sıralayın ve geçin
Sezgi
Bir kopyayı küçükten büyüğe sıralayın. En büyük değer sonda yer alır ve art arda birkaç kez bulunabilir. Sondan başlayarak en büyük değerin tüm kopyalarını geçip sola doğru ilerleyin; karşılaştığınız ilk farklı değer ikinci en büyük değerdir. [6, 6, 6, 3] için sıralanmış kopya [3, 6, 6, 6] olur: üç 6'yı geçer ve 3'e ulaşırsınız.
Buradaki klasik hata, sondan ikinci elemanı döndürmektir. [4, 9, 2, 7, 9] için bu, yine en büyük değer olan 9'u döndürür. Liste en az iki farklı değer içerdiğinden, sola doğru ilerlerken listenin başını geçmezsiniz.
Yanıt doğru olsa da, yalnızca en büyük iki değerle ilgilenirken sıralama tüm değerleri sıralar. Bu işlem O(n log n) zaman ve kopya için O(n) bellek maliyetine sahiptir.
Algoritma
nums'u kopyala ve kopyayı küçükten büyüğe sırala.iindeksini son konumda başlat.ikonumundaki değer maksimuma eşit olduğu sürece,i'yi bir adım sola taşı.ikonumundaki değeri döndür.
def secondLargest(nums):
ordered = sorted(nums)
i = len(ordered) - 1
# Step left past every copy of the maximum.
while ordered[i] == ordered[-1]:
i -= 1
return ordered[i]İki geçiş
Sezgi
İşi iki geçişe böl. İlk geçiş, En Büyük Sayıyı Bul örneğindeki gibi maksimumu bulur. İkinci geçiş, bu maksimumdan kesinlikle küçük olan en büyük değeri arar. [4, 9, 2, 7, 9] için ilk geçiş 9 değerini bulur; ikinci geçiş her iki 9 değerini de atlar ve 4, 2 ve 7 arasındaki en büyük değeri, yani 7 değerini tutar.
second değişkenini, listenin tutabileceği her değerden daha küçük bir değere ayarla; örneğin dilindeki en küçük tam sayı. Liste en az iki farklı değer içerir; dolayısıyla maksimumdan küçük bir değer vardır ve başlangıç değerinin yerini mutlaka alır.
Her geçiş, çalışan maksimumu bulur; bu nedenle toplam maliyet O(n) zaman ve O(1) alan kullanımıdır. Bunun karşılığında listeyi iki kez okumak gerekir; değerler birer birer gelip okunduktan sonra kayboluyorsa bu mümkün değildir.
Algoritma
numsüzerinde bir kez döngü kur ve maksimum değerilargestdeğişkeninde sakla.seconddeğişkenini izin verilen her değerden daha küçük bir değere ayarla.- Tekrar döngü kur.
x < largestvex > secondkoşullarını sağlayan herxiçinseconddeğerinixolarak ayarla. seconddeğerini döndür.
def secondLargest(nums):
largest = nums[0]
for x in nums:
if x > largest:
largest = x
second = float("-inf") # below every allowed value
for x in nums:
if x < largest and x > second:
second = x
return secondEn büyük iki değeri tek geçişte takip etme
Sezgi
Şimdiye kadar görülen en büyük iki farklı değer için largest ve second adlı iki değişken tutun. Her yeni x değeri üç durumdan birine girer. x, largest değerinden büyükse eski largest ikinci sıraya düşer ve en üst sıraya x geçer. x, second ile largest arasında, uç değerler hariç, yer alıyorsa yeni second olur. Diğer tüm durumlarda hiçbir şey değişmez.
Yinelenen değerleri doğru şekilde ele alan şey, katı karşılaştırmalardır. [4, 9, 2, 7, 9] için: largest önce 4, ardından second = 4 ile birlikte 9 olur. 2 hiçbir şeyi değiştirmez; 7, 4 ile 9 arasında yer aldığı için second = 7 olur ve son 9, largest değerine eşit olduğundan atlanır. Yanıt 7 olur.
Her iki değişkeni de mümkün olan tüm değerlerden daha küçük bir değerle başlatın. İkisini de 0 ile başlatmak, hiçbir değer 0'ı geçemeyeceği için [-5, -1, -8] için 0 döndürür. Liste iki farklı değer içerdiğinden, second sonunda her zaman listedeki gerçek bir değeri alır.
Algoritma
largestveseconddeğerlerini izin verilen tüm değerlerden daha küçük olarak ayarla.numsiçindeki herxdeğeri üzerinde döngü kur.x > largestiselargestdeğerinisecondiçine taşı velargestdeğerinixolarak ayarla.- Aksi takdirde,
x < largestvex > secondiseseconddeğerinixolarak ayarla. - Döngüden sonra
seconddeğerini döndür.
def secondLargest(nums):
# Both start below every allowed value.
largest = second = float("-inf")
for x in nums:
if x > largest:
second = largest # the old maximum drops to second place
largest = x
elif largest > x > second:
second = x
return second
Tuzaklar ve uç durumlar
Yanlış yanıtların çoğu, en büyük değerin tekrar etmesinden veya negatif değerlerden kaynaklanır.
- Sıralanmış listenin sondan bir önceki elemanını döndürmek. En büyük değer tekrarlandığında,
[4, 9, 2, 7, 9]örneğinde olduğu gibi, bu değer yine en büyük olur. - Değişkenleri
0ile başlatmak.[-5, -1, -8]listesinde hiçbir değer0'ı geçmez ve listede olmayan bir sayı olan0'ı döndürürsün. - İlk koşulda
x >= largestyazmak. Böylece ikinci bir9, ilk9'usecondiçine taşır ve9döndürürsün. seconddeğerini yalnızca yeni bir en büyük değer ortaya çıktığında güncellemek.[10, 20, 15]listesinde15,seconddeğerine hiç ulaşmaz ve10döndürürsün.- Bir kümeyle tekrarları kaldırıp sonra sıralamak. İşe yarar, ancak tek geçişte yapılabilecek bir işlem için
O(n)bellek veO(n log n)zaman harcar.
Sıkça sorulan sorular3
Bir dizideki ikinci en büyük sayıyı tek geçişte nasıl bulabilirsin?
Şimdiye kadar görülen en büyük ve ondan farklı ikinci en büyük değerleri tut. Bir değer en büyüğü geçtiğinde, eski en büyük değer ikinci sıraya geçer. Bir değer ikisinin kesin olarak arasında kaldığında, ikinci değerin yerini alır. Tek bir geçişin ardından ikinci değişken yanıtı tutar.
İkinci en büyük elemanı bulmanın zaman karmaşıklığı nedir?
Tek geçişli ve iki geçişli yöntemlerin her ikisi de O(n) zaman ve O(1) ek alan kullanır. Önce sıralama yapmak O(n log n) zaman alır. O(n) değerini geçemezsiniz; çünkü her değer en az bir kez okunmalıdır.
Yinelenen öğeler ikinci en büyük öğeyi nasıl etkiler?
Bu problem, birbirinden farklı en büyük ikinci değeri sorar; bu nedenle maksimum değerin tekrarları atlanır. [9, 9, 7] için cevap 7 olur. Sorunun bazı sürümlerinde bunun yerine konumlar sayılır ve cevap 9 olur; bu yüzden kod yazmadan önce hangisinin kastedildiğini kontrol et.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def secondLargest(nums):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
nums = [4, 9, 2, 7, 9]
Beklenen Çıktı
7