LeetCode 448 · Find All Numbers Disappeared in an Array · Easy
Çözümün her adımını burada izleyebilirsin. Bir dizi seç, İleri'ye bas ya da Oynat'a tıkla; gördüğümüz her sayının kutusunun nasıl işaretlendiğini ve işaretsiz kalan kutuların kayıp sayıları nasıl gösterdiğini gör.
Sayılar 1 ile n arasında, dizide de tam n kutu var. x sayısının kutusu nums[x - 1]: 1'in kutusu nums[0], 2'nin kutusu nums[1] ve böyle devam eder.
Bir sayıyı görünce kutusundaki değeri negatif yap. Değer kaybolmaz, sadece işareti değişir; okurken Math.Abs ile asıl sayıya geri dönersin.
nums[i] sonunda hâlâ pozitifse i + 1 sayısı dizide hiç yok demektir. Toplarken negatif kutuları da geri çevirip diziyi eski hâline getiriyoruz.
Virgülle ayrılmış en az 1, en fazla 10 tam sayı yaz. Her sayı 1 ile dizinin uzunluğu arasında olmalı; örneğin 3 elemanlı bir dizide sadece 1, 2 ve 3 olabilir.
nums (her kutunun altında hangi sayının kutusu olduğu yazıyor)
Değişkenler
Kod (Solution.cs içindeki metot)
Diziyi iki kez geziyoruz: O(n) zaman. İşaretleri ayrı bir dizide değil, nums'ın kendi kutularında, sayının işaretinde tutuyoruz. Fazladan sadece num, box ve i gibi birkaç değişken var: O(1) ekstra bellek. Döndürdüğümüz liste bu hesaba katılmıyor.
Daha kolay bir çözüm de var: görülen sayıları bool[] seen = new bool[n + 1] dizisinde işaretleyip sonra false kalanları toplamak. O da O(n) zamanda çalışır ama n + 1 elemanlık ayrı bir dizi açtığı için O(n) bellek kullanır. Bu sayfadaki çözüm aynı işaretlemeyi nums'ın içinde yaptığı için o diziye gerek kalmıyor.
İkinci döngüde negatif kutuları yeniden pozitife çeviriyoruz. Böylece metodu çağıran kod dizisini verdiği gibi geri alıyor. Bunun için ayrı bir döngü de gerekmiyor; kayıp sayıları toplarken aynı turda yapılıyor.