Find the Duplicate Number

Tekrarlanan değer en az iki konumda bulunur: i < j. Her konumu, kendisinden sonraki her konumla karşılaştır; eşit değerleri içeren ilk çift yanıtı verir. İlk örnekte 1. konumda 5 bulunur ve 2. konumdan itibaren yapılan tarama, 4. konumda başka bir 5 bulur.

Bu, her iki kuralı da korur: hiçbir şey yazılmaz ve kullanılan tek bellek iki döngü sayacıdır. Çiftleri karşılaştırdığı için yavaştır. n+1 = 10.001 değer ve her iki kopya da sona yakın olduğunda, yaklaşık 5 × 10^7 çift kontrol eder.

Konumları değil, değer aralığını araştırın. Bir kesme değeri m seçin ve nums içindeki kaç öğenin en fazla m olduğunu sayın.

Tekrarlanan d değeri m'den büyükse, 1 ile m arasındaki her değer en fazla bir kez görünür; bu nedenle sayı en fazla m'dir. d en fazla m ise, m'den büyük her değer en fazla bir kez görünür; bu nedenle en fazla n-m öğe m'den büyüktür ve en az m+1 öğe en fazla m'dir. Dolayısıyla "count > m" testi, d'den küçük her m için yanlıştır ve d'den itibaren doğrudur. İkili arama, doğru olduğu ilk m değerini bulur; bu da d'dir.

İkinci örnekte n 4'tür. m = 2 için 2 ve 1 öğeleri, 2 sayısını verir; bu 2'den fazla değildir, dolayısıyla yanıt 2'den büyüktür. m = 3 için sayı yine 2'dir, dolayısıyla yanıt 4'tür. Her turda dizinin tamamı bir kez okunur ve aralık yarıya indirilir; bu nedenle iş miktarı O(n log n)'dir: 10.001 değer üzerinde yaklaşık 14 geçiş.

Diziyi bağlantılar olarak oku: i konumu, nums[i] konumuna işaret eder. 0'dan n'ye kadar her konumun tam olarak bir çıkış bağlantısı vardır ve her bağlantı 1 ile n arasındaki bir konuma ulaşır. İlk örnekte bağlantılar 0 → 2, 1 → 5, 2 → 1, 3 → 3, 4 → 5 ve 5 → 4 şeklindedir.

0 konumundan başla ve bağlantıları takip et. Her konumun bir bağlantısı olduğundan bu yürüyüş asla duramaz ve yalnızca n+1 konum olduğundan daha önce gördüğü bir konuma geri dönmek zorundadır. O andan itibaren sonsuza kadar döngüde ilerler. Yol, ρ harfi biçiminde, bir kuyruk ve ardından bir döngüden oluşur. İlk örnekte yürüyüş 0, 2, 1, 5, 4, 5, 4 ve böyle devam eder: kuyruk 0, 2, 1; döngü ise 5, 4'tür. 3 konumu kendisine bağlantı verir ama yürüyüş oraya hiç ulaşmaz; bunun bir zararı yoktur.

Döngünün giriş noktası yinelenen değerdir. Yürüyüş 5'e farklı yerlerden iki kez girer: bir kez kuyruğun sonundan (1. konum, çünkü nums[1] değeri 5'tir) ve bir kez döngünün sonundan (4. konum, çünkü nums[4] değeri 5'tir). İki farklı konum 5 değerini içerdiğinden 5 yinelenir. Kuyrukta her zaman 0 konumu bulunur; çünkü hiçbir değer 0 değildir ve hiçbir bağlantı 0'a geri dönmez. Bu nedenle giriş noktasına her zaman bu iki farklı yoldan ulaşılır. Tam olarak bir değer yinelendiğinden giriş noktası bu değerdir.

Şimdi bağlantılı listedeki döngü tespitinde olduğu gibi iki işaretçiyle giriş noktasını bul. 1. aşamada slow her turda bir bağlantıyı, fast ise iki bağlantıyı takip eder; ikisi döngünün bir yerinde aynı konumda durana kadar devam eder. İlk örnekte 4'te buluşurlar. 2. aşamada slow'u 0'a geri koy, fast'i olduğu yerde bırak ve ikisini de her turda bir bağlantı ilerlet. Giriş noktasında buluşurlar.

2. aşamanın neden işe yaradığını açıklayalım: kuyruğun giriş noktasına ulaşması için T bağlantı gerektiğini ve döngünün C konumu olduğunu varsayalım. İşaretçiler buluştuğunda slow s adım, fast ise 2s adım atmıştır. İkisi de aynı noktada durduğuna göre fast'in attığı fazladan s adım, döngünün tam tur sayısına karşılık gelir. T adım daha sonra slow, 0'dan giriş noktasına ulaşır; fast ise fazladan turları bir şeyi değiştirmediğinden, 0'dan başlayan bir yürüyüşün s+T adım sonundaki konumunda durur. Bu, giriş noktasına ulaşmak için T adım ve ardından s adım, yani tam tur sayısı kadar adımdır; dolayısıyla fast de giriş noktasında olur. Daha önce buluşamazlar; çünkü slow hâlâ kuyruktayken fast döngüden hiç çıkmaz. İlk örnekte slow 2, 1, 5 konumlarından geçerken fast 5, 4, 5 konumlarından geçer ve T = 3 adım sonra 5'te buluşurlar.

Her aşama O(n) adım sürer, kullanılan tek bellek iki konumdur ve nums üzerine hiçbir zaman yazılmaz.