Yinelenenleri Yerinde Kaldırma

Sıralanmış bir dizi verildiğinde, ek bir dizi kullanmadan her değerin bir kopyasını koruyun. İşlemi yerinde yapmak bellek tasarrufu sağlar ve mülakatlarda sık sorulan klasik bir görevdir. 🧹

Dizi sıralı olduğunda her yinelenen değer kendi eşinin hemen yanında bulunur. Böylece tüm diziyi değil, yalnızca komşuları karşılaştırırsınız.

Son korunan değeri gösteren yavaş bir işaretçi ve ileride yeni bir şey arayarak tarama yapan hızlı bir işaretçi kullanın.

yavaş işaretçiyi yazma konumu olarak düşünün: kendisinin öncesindeki ve bulunduğu konumdaki her şey zaten temizlenmiş ve tektir.

hızlı işaretçi yalnızca ileri doğru okur. Önden ilerler ve henüz korunmamış bir değer gördüğünde yavaşa haber verir.

a[fast], a[slow] değerine eşitse bu bir tekrardır; hızlı işaretçiyi ilerletmek dışında hiçbir şey yapmayın. Yinelenen değer sessizce atlanır.

a[fast] farklı olduğunda yavaşı ilerletin ve yeni değeri oraya kopyalayın. Böylece eski yinelenen değerlerin üzerine yeni ve tekil veriler yazılır.

Tarama sonrasında slow + 1, dizinin başında toplu hâlde bulunan tekil değerlerin sayısıdır.

Tekil önekten sonra kalan her şey artık gereksiz veridir. Problem yalnızca ilk slow + 1 öğeyle ilgilenir; bu nedenle kuyruğu olduğu gibi bırakın.

Boş bir dizide hiç tekil değer yoktur. Başlamadan önce n == 0 durumunu kontrol edin; böylece dizinin sonunun ötesini okumazsınız.

Bu yavaş-hızlı kalıbı O(n) zamanda ve O(1) ek alanla çalışır; sıkı bellek sınırlarının gerektirdiği tam olarak budur.

Sıralanmış bir dizide yavaş ve hızlı işaretçilerle yinelenenleri yerinde kaldırıyorsunuz.

Sıralanmış bir dizide yavaş-hızlı işaretçi çifti, ek alan kullanmadan tek bir O(n) geçişinde yinelenenleri kaldırır ve tekil değerlerin sayısı olarak slow + 1 döndürür. 🎉