Dublikat Nömrəni tapın LeetCode Həll

Problem bəyanat

Dublikat Nömrəni tapın LeetCode Həll - Tam ədədlər massivi nəzərə alınmaqla nums olan n + 1 hər bir tamın diapazonda olduğu tam ədədlər [1, n] daxildir.

Yalnız var bir təkrar nömrə in nums, qayıt bu təkrarlanan nömrə.

Problemi həll etməlisiniz olmadan massivin dəyişdirilməsi nums və yalnız daimi əlavə yerdən istifadə edir.

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

Izahat

İdeya problemi Əlaqəli Siyahı Cycle II-ə endirməkdir:

Verilmiş a əlaqəli siyahı, olduğu node qayıt dövrü başlayır.

Əvvəla, dövran haradan gəlir? funksiyasından istifadə edək f(x) = nums[x] ardıcıllığı qurmaq üçün: x, nums[x], nums[nums[x]], nums[nums[nums[x]]], ....

Ardıcıllığın hər bir yeni elementi indeksində ədədlərlə bir elementdir əvvəlki element.

Birindən başlasa x = nums[0], belə bir ardıcıllıq dövrü ilə əlaqəli siyahı yaradacaq.

Dövr ona görə görünür nums dublikatları ehtiva edir. Dublikat node dövrə girişidir.

Burada çalışır necə:

Pin

Alqoritm

Floydun alqoritmi iki mərhələdən ibarətdir və adətən adlanan iki göstəricidən istifadə edir tortoise və hare.

1-ci mərhələdə, hare = nums[nums[hare]] iki dəfə sürətlidir tortoise = nums[tortoise]. Dovşan sürətlə getdiyi üçün dövrəyə ilk girən və dövrənin ətrafında qaçan o olardı. Bir anda tısbağa da dövrəyə girir və yavaş hərəkət etdiyi üçün dovşan bir anda tısbağaya çatır. kəsişmə nöqtə. İndi 1-ci mərhələ bitdi və tısbağa uduzdu.

Kəsişmə nöqtəsini hesablamaq üçün qeyd edək ki, dovşan tısbağadan iki dəfə çox düyün keçib. yəni $2d(\text{tısbağa})=d(\text{dovşan})$, nəzərdə tutur:

$2(F+a)=F+nC+a$, Harada $n$ bəzi tam ədəddir.

2-ci mərhələdə, biz dovşanı yavaşlatmaqla tısbağaya ikinci şans veririk ki, indi tısbağanın sürəti ilə hərəkət etsin: tortoise = nums[tortoise], hare = nums[hare]. Tısbağa başlanğıc mövqeyinə qayıdır, dovşan isə kəsişmə nöqtəsindən başlayır.

Göstərək ki, onlar bu dəfə velosipedin girişində görüşürlər $F$ addımlar.

• Tısbağa sıfırdan başladı, buna görə də sonra onun mövqeyi $F$ addımlardır $F$.
• Dovşan kəsişmə nöqtəsindən başladı $F+a=nC$, belə ki, onun F addımlarından sonrakı mövqeyidir $nC+F$ilə eyni nöqtədir $F$.
• Beləliklə, tısbağa və (yavaşlamış) dovşan dövrün girişində görüşəcəklər.

Kodu

Dublikat nömrəni tapmaq üçün C++ kodu

class Solution {
public:
    int findDuplicate(vector<int>& nums) {

        // Find the intersection point of the two runners.
        int tortoise = nums[0];
        int hare = nums[0];

        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);

        // Find the "entrance" to the cycle.
        tortoise = nums[0];
        while (tortoise != hare) {
            tortoise = nums[tortoise];
            hare = nums[hare];
        }

        return hare;
    }
};

Dublikat nömrəni tapmaq üçün Java kodu

class Solution {
    public int findDuplicate(int[] nums) {
        
        // Find the intersection point of the two runners.
        int tortoise = nums[0];
        int hare = nums[0];
        
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);

        // Find the "entrance" to the cycle.
        tortoise = nums[0];
        
        while (tortoise != hare) {
            tortoise = nums[tortoise];
            hare = nums[hare];
        }

        return hare;
    }
}

Dublikat nömrəni tapmaq üçün Python kodu

class Solution:
    def findDuplicate(self, nums):
        # Find the intersection point of the two runners.
        tortoise = hare = nums[0]
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if tortoise == hare:
                break
        
        # Find the "entrance" to the cycle.
        tortoise = nums[0]
        while tortoise != hare:
            tortoise = nums[tortoise]
            hare = nums[hare]
        
        return hare

Dublikat Nömrəni Tapmaq üçün Mürəkkəblik Təhlili LeetCode Həlli

Zamanın mürəkkəbliyi

O (n)

Kosmik Mürəkkəblik

O (1)