Find the Largest Number
Boş olmayan bir tam sayı listesi nums alırsın. İçindeki en büyük değeri döndür. Değerler negatif olabilir, dolayısıyla cevap da negatif olabilir. max gibi yerleşik bir maksimum fonksiyonu kullanmadan, kendi karşılaştırmalarınla bul.
Fonksiyon
- numsinteger-array
- aranacak tam sayıların listesi
- Döndürürinteger
- nums içindeki en büyük değer
Kısıtlar
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Örnekler
- Girdi
- nums = [3, 17, 4, 12, 9]
- Çıktı
- 17
- Açıklama
- Soldan okuyunca, şimdiye kadarki en büyük değer önce
3, ardından17olur.4,12veya9değerlerinin hiçbiri17'yi geçemez; bu yüzden cevap17'dir.
- Girdi
- nums = [-8, -3, -11, -3]
- Çıktı
- -3
- Açıklama
- Tüm değerler negatiftir ve
-3sıfıra en yakın olanıdır, dolayısıyla en büyüğüdür. İki kez görünür, ancak konumunu değil, değeri döndürürsün.
- Girdi
- nums = [42]
- Çıktı
- 42
- Açıklama
- Tek bir değere sahip bir listenin en büyük değeri, o değerin kendisidir.
Gönderirken +13 gizli test
Ek soru
Değerleri önce ikişer ikişer karşılaştırarak yaklaşık 3n/2 karşılaştırma yerine 2n karşılaştırmayla hem en büyük hem de en küçük değeri döndürebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Değerleri teker teker okuyun. Daha önce gördüğünüz değerlerle ilgili hatırlamanız gereken tek şey nedir?
Şimdiye kadarki en büyük değeri aklında tut. Her yeni değer ya onu geçer ya da geçemez.
Çalışan maksimumu
nums[0]ile başlat,0ile değil; çünkü tüm değerler negatif olabilir. Her değerle karşılaştır ve büyük olanı tut.
Çözüm
Atladığın herhangi bir değer en büyük değer olabilir, bu yüzden her çözüm her öğeyi en az bir kez okur. Asıl karar, geçerli maksimumun nerede başlayacağıdır. İlk öğeden başlat, asla 0 değerinden değil; çünkü listedeki tüm değerler negatif olabilir.
Bir kopyayı sıralayın ve son değeri alın
Sezgi
Küçükten büyüğe sıralanmış bir listede en büyük değer sondadır. Çağıranın listesi olduğu gibi kalsın diye nums listesini kopyalayın, kopyayı sıralayın ve son öğesini döndürün. [3, 17, 4, 12, 9] için sıralanmış kopya [3, 4, 9, 12, 17] olur ve son öğe 17'dir.
Yanıt doğru, ancak sıralama ihtiyacınızdan çok daha fazlasını yapar. Her değeri sıralar; bu da yaklaşık n log n karşılaştırma gerektirir. n = 5000 için bu yaklaşık 60,000 karşılaştırmadır, oysa yalnızca en büyük değeri istiyorsunuz. Kopya ayrıca O(n) bellek kullanır.
JavaScript ve TypeScript'te sort yöntemine bir karşılaştırıcı iletin. Karşılaştırıcı olmazsa sayıları metin olarak karşılaştırır ve bu da 12 ile 17'yi 3'ün önüne koyar.
Algoritma
nums'un bir kopyasını oluştur.- Kopyayı, sayıları sayı olarak karşılaştırarak küçükten büyüğe sırala.
- Sıralanmış kopyanın son elemanını döndür.
def findMax(nums):
ordered = sorted(nums) # a sorted copy, smallest first
return ordered[-1]Bir geçişte güncel maksimumu tutma
Sezgi
Şimdiye kadar görülen en büyük değer için largest adlı tek bir değişken kullan. Değişkeni nums[0] ile başlat, her değerle karşılaştır ve daha büyük bir değerle karşılaştığında değişkenin değerini güncelle. Döngü sona erdiğinde largest her elemanla karşılaştırılmış olur; dolayısıyla listedeki hiçbir değer onu geçemez.
[3, 17, 4, 12, 9] için largest başlangıçta 3 olur, sonra 17 değerini alır ve 4, 12 ve 9 boyunca 17 olarak kalır. Bu, n-1 yararlı karşılaştırma ve bir ek değişken demektir.
nums[0] ile başlamak, negatif sayılardan oluşan listelerin de doğru çalışmasını sağlar. Bunun yerine 0 ile başlatırsan, [-8, -3, -11, -3] listesindeki hiçbir değer bu değeri geçemez; bu nedenle listede bile olmayan 0 değerini döndürürsün.
Algoritma
largestdeğerininums[0]olarak ayarla.numsiçindeki herxdeğerinin üzerinden geç.x > largestiselargestdeğerinixolarak ayarla.- Döngüden sonra
largestdeğerini döndür.
def findMax(nums):
largest = nums[0] # never 0: every value may be negative
for x in nums:
if x > largest:
largest = x
return largest
Tuzaklar ve uç durumlar
Döngü kısa olduğundan hatalar, döngünün nerede başladığında ve neyi okuduğunda saklıdır.
largestdeğerini0veya-1olarak başlatmak. Değerlerinin tümü bu başlangıç değerinden küçük olan her liste, listede bulunmayan bir sayı döndürür.-1000000gibi uydurma, küçük bir sayıyla başlatmak. Buradaki değerler-10^9değerine kadar iner, dolayısıyla başlangıç değeri yine daha büyük kalır.nums[0]için tahminde bulunmak gerekmez.- İlk elemanın
nums[1]olduğu Lua veya R'denums[0]değerini okumak. Luanil, R ise boş bir vektör döndürür. - 0 tabanlı indeksler kullanan bir dilde
i ≤ nile döngü kurmak; bu, son elemandan sonraki bir elemanı okumaya çalışır. - JavaScript veya TypeScript'te sayısal bir karşılaştırıcı olmadan sıralama yapmak.
[3, 17, 4, 12, 9]dizisinin metin sıralamasında son sırada9yer alır; bu nedenle17yerine9döndürürsünüz.
Sıkça sorulan sorular4
Dizideki en büyük değeri bulmanın zaman karmaşıklığı nedir?
Tek bir geçiş O(n) zaman ve O(1) ek alan alır. Sıralanmamış bir dizide hiçbir yöntem daha iyisini yapamaz; çünkü hiç okumadığınız herhangi bir eleman en büyük olabilir. Önce sıralamak O(n log n) maliyetlidir ve hiçbir kazanç sağlamadan daha yavaştır.
max kullanmadan bir dizideki en büyük sayıyı nasıl bulabilirsin?
İlk öğeyi bir değişkende saklayın. Geri kalan öğeler üzerinde döngü kurun ve bir öğe değişkendekinden büyük olduğunda o öğeyi saklayın. Döngü sona erdiğinde, değişken en büyük değeri tutar.
Çalışan maksimum neden 0 yerine ilk elemandan başlamalı?
Her değer negatifse hiçbiri 0'dan büyük değildir; bu nedenle 0 ile başlayan maksimum değer hiç değişmez ve işlev 0 döndürür. İlk eleman her zaman gerçek bir adaydır, bu yüzden oradan başlamak her liste için doğrudur. Listenin hiçbir zaman boş olmaması koşuluyla, dilinizdeki en küçük tam sayı da işe yarar.
En büyük değeri bulmak için sıralama ne zaman iyi bir yöntemdir?
En büyük üç değer veya medyan gibi en büyük değerden fazlasına ihtiyaç duyduğunuzda ve aynı liste hakkında bu tür birçok soru soracağınızda. Tek bir maksimum değer için bir geçiş daha hızlıdır ve listeyi olduğu gibi bırakır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def findMax(nums):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
nums = [3, 17, 4, 12, 9]
Beklenen
17