Leetcode 287 Find the Duplicate Number

Soru

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Örnek 1

Input: nums = [1,3,4,2,2]
Output: 2

Örnek 2

Input: nums = [3,1,3,4,2]
Output: 3

Örnek 2

Input: nums = [1,1]
Output: 1

Çözüm

• Bir dizide tekrar eden tek bir sayıyı bulmanızı ister. Dizide tam olarak bir sayı birden fazla kez tekrar eder ve sorunun amacı bu sayıyı bulmaktır. Dizi, 1 ile n arasındaki sayıları içerir ve dizinin uzunluğu n+1’dir. Yani, n tane farklı sayı ve bunlardan biri tekrar eden sayı olarak verilmiştir.
• Girdi: Tekrar eden bir sayı içeren bir tam sayı dizisi nums.
• Çıktı: Tekrar eden sayı.
• Bu problem birkaç farklı yöntemle çözülebilir, ancak en etkili yöntemlerden biri “Floyd’un Çevrim Tespiti Algoritması” (aynı zamanda tortoise ve hare algoritması(hızlı-yavaş) olarak da bilinir) kullanmaktır. Bu yöntem, bir bağlı liste içinde döngü bulmak için genellikle kullanılır, ama dizilerde de uygulanabilir. Dizi indeksleri ve değerleri bir tür “bağlı liste” olarak düşünüldüğünde, dizi içinde bir çevrim tespit edilerek tekrar eden eleman bulunabilir.
• Çalışma Mekanizması:
• İlk Faz - Çevrim Tespiti:
• tortoise (yavaş işaretçi) her adımda bir sonraki elemana ilerler: tortoise = nums[tortoise].
• hare (hızlı işaretçi) her adımda iki sonraki elemana atlar: hare = nums[nums[hare]].
• Bu iki işaretçi, dizide bir çevrim (döngü) oluşturan tekrar eden sayı nedeniyle bir noktada eşit olacaktır.
• İkinci Faz - Çevrimin Başlangıç Noktasını Bulma:
• Çevrim içinde bir noktada eşit olan hare ve tortoise işaretçilerinden biri dizinin başına konur.
• Her iki işaretçi de artık birer adım ilerleyecektir. Bir sonraki buluşma noktaları, çevrimin başladığı yani tekrar eden sayının bulunduğu konum olacaktır.

Code

class Solution:
    def findDuplicate(self, nums):
        # Hare ve tortoise başlatılıyor
        slow = fast = nums[0]
        
        # Hızlı ve yavaş işaretçi ilk buluşma noktasına kadar ilerletiliyor
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        # İkinci faz: çevrimin başlangıç noktasını bul
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return fast

Complexity

• Time complexity (Zaman Karmaşıklığı): O(n), burada n dizinin uzunluğudur. İşaretçiler diziyi yalnızca birkaç kez tarayacaktır.
• Space complexity (Alan Karmaşıklığı): O(1), çünkü ekstra alan kullanılmadan, yalnızca birkaç işaretçi ile çözüm üretilir.