Missing Number
Her biri 0 ile n arasında olan, birbirinden farklı n tam sayıdan oluşan bir nums listesi veriliyor. 0 ile n arasındaki aralıkta n+1 sayı bulunduğundan, bunlardan tam olarak biri listede yoktur. Eksik olan bu sayıyı döndürün.
Fonksiyon
- numsinteger-array
- 0 ile n aralığından, herhangi bir sırada n farklı tam sayı
- Döndürürinteger
- nums içinde bulunmayan 0 ile n arasındaki tek sayı
Kısıtlar
n == nums.length1 ≤ n ≤ 1040 ≤ nums[i] ≤ n- Tüm
numsdeğerleri birbirinden farklıdır.
Örnekler
- Girdi
- nums = [4, 2, 0, 1]
- Çıktı
- 3
- Açıklama
- Listede 4 değer var, bu nedenle aralık 0 ile 4 arasındadır. 0, 1, 2 ve 4 değerlerini içerir; eşleşmesi olmayan tek sayı 3'tür.
- Girdi
- nums = [1]
- Çıktı
- 0
- Açıklama
- Tek bir değerle aralık 0 ve 1'dir. Liste 1'i içerir, dolayısıyla 0 eksiktir.
- Girdi
- nums = [0, 1, 2]
- Çıktı
- 3
- Açıklama
- 3'ün altındaki her sayı mevcut, bu nedenle eksik olan sayı aralığın üst sınırı olan 3'ün kendisidir. Bu, listenin bir indeksi değildir; bu yüzden üst sınıra dikkat etmek gerekir.
Gönderirken +13 gizli test
Ek soru
Sıralanmış bir liste olsaydı, ikili aramayla eksik sayıyı O(log n) sürede bulabilir miydin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Listenin hangi sayıları içermesi gerektiğini tam olarak biliyorsun:
0ilenarasındaki her tam sayı. Bu aralığın tamamı için hesaplayabileceğin ve liste için hesaplanan aynı sayıyla karşılaştırabileceğin bir sayı var mı?0'dann'ye kadar olan tam sayılarn(n+1)/2toplamını verir ve listenin toplamı eksik değer kadar daha küçüktür. XOR, bir değerin kendisiyle XOR'lanması0olduğundan taşma riski olmadan aynı şekilde çalışır.Listeyi çalışan bir XOR ile bir kez dolaşın. Başlangıç değerini
nolarak ayarlayın ve heriindeksinde hemihem denums[i]değerini XOR işlemine dahil edin. İki kez görünen her sayı birbirini götürür ve eksik olan sayı geriye kalır.
Çözüm
Listenin tam olarak neleri içermesi gerektiğini biliyorsun: 0 ile n arasındaki her tam sayı. Bu sayıların her birini tek tek aramak işe yarar, ancak her sayı için listeyi baştan sona tekrar tarar. Bunun yerine, tüm aralığı ve listeyi tek bir özet değerle ifade et: toplamları ya da XOR’ları. İkisi arasındaki fark, eksik sayıyı verir. Bu yöntem tek geçiş gerektirir ve ek bellek kullanmaz.
Her adayı kontrol et
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Yanıt, 0 ile n arasındaki n+1 sayıdan biridir. Bunları sırayla ele alın ve her biri için listeyi tarayın. Hiçbir değerle eşleşmeyen ilk aday, eksik sayıdır.
Bu yöntem doğrudur; çünkü aralıktaki her sayı ya listede bulunur ya da yanıttır ve listede yinelenen değer olmadığından arama tam olarak bir aday için başarısız olur.
Yavaştır; çünkü her aday için en fazla n değerin taranması gerekir. Eksik sayı aralığın üst ucuna yakınsa, neredeyse her aday aranır: n = 10^4 ve eksik sayı sona yakın olduğunda bu, yaklaşık 5 × 10^7 karşılaştırma demektir. Listenin uzunluğunu iki katına çıkarmak işi dört katına çıkarır.
Algoritma
candidatedeğerini0'dann'e kadar (n dahil) döngüye sokun.numsiçindecandidate'e eşit bir değer arayın.- Arama değeri bulursa sonraki adaya geçin.
- Arama eşleşme bulamadan sona ererse
candidate'i döndürün.
def missingNumber(nums):
n = len(nums)
for candidate in range(n + 1):
# "in" on a list scans it from the start: O(n) per candidate.
if candidate not in nums:
return candidate
return -1Beklenen toplamdan toplamı çıkarın
Sezgi
Hiçbir sayı eksik olmasaydı liste, 0 ile n arasındaki tüm sayıları içerirdi ve bunların toplamı n(n+1)/2 olurdu. Gerçek liste, bu tam kümeden bir sayı çıkarılmış hâlidir; dolayısıyla toplamı tam olarak o sayı kadar eksik kalır.
[4, 2, 0, 1] için n 4'tür ve tam aralığın toplamı 4 × 5 / 2 = 10 eder. Listenin toplamı 7'dir; 10'dan 7 çıkarıldığında 3 kalır.
Tek bir geçişte listeyi toplarsın; dolayısıyla zaman karmaşıklığı O(n) olur ve tek bir değişken toplam tutarsın. Burada tam toplam en fazla yaklaşık 5 × 10^7 olur; bu değer 32 bitlik bir tamsayıya sığar. Çok daha büyük n değerlerinde formül 32 bitlik bir tamsayıda taşmaya yol açar; bu nedenle Java, C, C++, C# ve Rust sürümleri hesaplamayı 64 bitte yapar.
Algoritma
n,numsuzunluğu olsun.- Tam toplamı
n(n+1)/2hesapla. numsiçindeki tüm değerleri topla.- Tam toplamdan listenin toplamını çıkarıp döndür.
def missingNumber(nums):
n = len(nums)
expected = n * (n + 1) // 2
return expected - sum(nums)İndeksleri değerlerle XOR işlemine tabi tutun
Sezgi
XOR çiftleri yok eder. a ^ a, 0'dır; a ^ 0, a'dır ve işlemlerin sırası önemli değildir. Dolayısıyla, bir sayı torbasındaki her şey bir değer dışında iki kez görünüyorsa bu sayıları XOR'ladığında çiftler yok olur ve geriye o değer kalır.
Problemdeki bilgilerden böyle bir torba oluştur: 0 ile n arasındaki indeksler ve nums içindeki değerler. Listede bulunan bir sayı hem indeks olarak hem de değer olarak bir kez görünür, dolayısıyla birbirini yok eder. Eksik sayı yalnızca indeks olarak görünür, dolayısıyla geriye kalır. Döngü 0 ile n-1 arasındaki indeksleri ziyaret eder; bu yüzden son indeksi de kapsamak için sonucu n ile başlat.
[4, 2, 0, 1] için: 4 ile başla, ardından 0 ve 4'ü, 1 ve 2'yi, 2 ve 0'ı, 3 ve 1'i XOR'la. 4'ler, 2'ler, 1'ler ve 0'lar birbirini yok eder; geriye 3 kalır. Bu, tek bir geçiş ve sürekli güncellenen tek bir değer kullanır. Toplamdan farklı olarak, n'nin zaten kullandığı bitlerin ötesine asla büyümez; bu nedenle taşma yaşanamaz.
Algoritma
resultdeğerinin, yaninumsuzunluğu olarak ayarla.- Her
iindeksi içinresultilei'yi venums[i]'yi XOR işlemine tabi tut. resultdeğerini döndür.
def missingNumber(nums):
# Start with n, the one index the loop below never reaches.
result = len(nums)
for i, value in enumerate(nums):
result ^= i ^ value
return result
Tuzaklar ve uç durumlar
Yanlış yanıtların çoğu aralığın iki ucundan kaynaklanır.
ndeğerinin kendisinin eksik olabileceğini unutmak.[0, 1, 2]dizisinde yanıt 3'tür ve bu, listenin bir indeksi değildir. XOR sürümündeğerinden başlamalıdır;nums[i] != ikoşulunun sağlandığı ilk konumu arayan sıralı tarama ise tüm konumlar eşleştiğindendöndürmelidir.- Yanlış aralık boyutunu kullanmak. Sayılar
0ilenarasında değişir; yanin+1sayı vardır. Bu nedenle toplamn(n+1)/2olur,(n-1)n/2değil. 0değerinin her zaman bulunduğunu varsaymak.[1]dizisinde yanıt 0'dır ve aramaya 1'den başlayan kod bunu bulamaz.- Toplam sürümünde taşma. 32 bit aritmetikte
n(n+1)çarpımı, 2'ye bölme işlemi işe yaramadan önce,nyaklaşık 46.000'i geçtiğinde taşar;n(n+1)/2ifadesinin kendisi de yaklaşık 65.000'de sığmaz hâle gelir. 64 bit aritmetik veya XOR kullanın.
Sıkça sorulan sorular4
Eksik Sayı'nın zaman karmaşıklığı nedir?
Toplam ve XOR çözümleri, her değeri bir kez okudukları ve tek bir sayı tuttukları için O(n) zamanda ve O(1) ek alanla çalışır. Her aday için listede arama yapmak O(n²) zaman alır. Önce sıralayıp ardından boşluğu aramak O(n log n) zaman alır.
XOR neden eksik sayıyı bulur?
Bir sayıyı kendisiyle XOR’lamak 0 verir, 0 ile XOR’lamak hiçbir şeyi değiştirmez ve sıra önemli değildir. 0’dan n’ye kadar tüm indeksleri listedeki tüm değerlerle XOR’ladığında, listede bulunan her sayı iki kez görünür ve birbirini götürür. Eksik sayı yalnızca bir kez, indeks olarak görünür; dolayısıyla sonuç odur.
Toplam formülünü mü yoksa XOR'u mu kullanmalısınız?
Her ikisi de tek geçiş ve sabit bellek kullanır. Toplamı açıklamak daha kolaydır, ancak 32 bit aritmetikte n(n+1) çarpımı, n yaklaşık 46.000'i aştığında taşar; bu nedenle 64 bit aritmetik kullanmanız gerekir. XOR hiçbir zaman taşmaz. Python, Ruby ve sınırsız tamsayıları destekleyen diğer dillerde bu fark ortadan kalkar.
Eksik Sayı problemini bir hash set ile çözebilir misin?
Evet. Her değeri bir kümeye koyun, ardından 0'dan n'ye kadar kontrol edin ve kümede bulunmayan ilk sayıyı döndürün. Bu yöntem O(n) zamanda çalışır ancak toplam ve XOR yöntemlerinin kaçındığı O(n) ek bellek kullanır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def missingNumber(nums):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
nums = [4, 2, 0, 1]
Beklenen
3