Mənim LeetCode 41 Tutqunum: İlk İtirilmiş Müsbət Tapmacanın Dərin Araşdırması

LeetCode-un "İlk İtən Müsbət Ədəd" problemi (41 nömrəli) son kodlaşdırma həvəsimə çevrilib. Aldadıcı dərəcədə sadə bir tapmaca olmasına baxmayaraq, düşüncələrimi tamamilə ələ keçirib, məni onun incəliklərini araşdırmağa və mümkün olan ən effektiv TypeScript həlli yaratmağa sövq edib. Bu yazı sadəcə kodlaşdırma müsahibələrində uğur qazanmaqla bağlı deyil (hərçənd bu yaxşı bir əlavədir). Bu, problem həll etmənin saf sevinci, optimallaşdırmanın həyəcanı və effektiv kodu gözəllik haqqındadır. Və bir az riyaziyyat həvəskarı olduğum üçün həllin riyazi əsaslarını da araşdıracağıq.

Problem: Qoyun dərisində canavar

Problem, ədədlərin qarışıq olmayan bir massivi təqdim edir. Sizin tapşırığınız: ən kiçik itən müsbət tam ədədi tapmaqdır. Sadə görünür? Yenidən düşünün. $O(n)$ vaxt və $O(1)$ yaddaş mürəkkəbliyi məhdudiyyətləri bu görünüşdə sadə tapşırığı çətin bir alqoritmik tapmacaya çevirir.

İlkin Çətinliklər: Brüt Qüvvə Tələsi

İlkin cəhdlərim sıralama ( $O(n)$ vaxt məhdudiyyətini pozur) və hash çoxluqlarını ( $O(1)$ yaddaş həddini aşır) əhatə edirdi. Aydındır ki, daha mürəkkəb bir yanaşma tələb olunurdu.

Evrika Anı: Yerdəyişmə Transformasiyası

Əsas anlayış, giriş massivini özü hash cədvəli kimi istifadə edə biləcəyimi başa düşmək oldu. Elementləri yenidən düzərək, $x$ ədədini $x - 1$ indeksində yerləşdirə bilərəm ($1 \le x \le n$, burada $n$ massivin uzunluğudur). Bu yerdəyişmə transformasiyası effektiv bir həll yoluna aparan yolu açır.

Kod Evolyusiyası: TypeScript Sazas

Budur, kodumun inkişaf tarixçəsi, ətraflı izahlar və riyazi anlayışlarla:

1-ci Versiya: Sadəlövh Yanaşma (Artıq Yerdəyişmələrlə)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length

  // Hər bir ədədi, əgər [1, n] aralığındadirsa, düzgün mövqeyinə yerləşdirin
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const correctIndex = nums[i] - 1
      ;[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]] // Yerdəyişmə
    }
  }

  // İlk itən müsbəti tapın
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Əgər bütün ədədlər düzgün mövqelərindədirsə, itən ədəd n + 1-dir
  return n + 1
}

Bu versiya, işlək olsa da, artıq yerdəyişmələrdən əziyyət çəkir. Ən pis hal ssenarisində yerdəyişmələrin sayı $O(n^2)$-yə yaxınlaşır, baxmayaraq ki, orta hal $O(n)$-yə daha yaxındır.

İzah:

1. Massivi yenidən düzün: Hər bir nums[i] ədədi, əgər [1, n] aralığında və hələ də düzgün mövqedə deyilsə, "düzgün" indeksində (nums[i] - 1) yerləşdirilir.

2. İtən müsbəti müəyyən edin: Yenidən düzəldilmədən sonra, nums[i] !== i + 1 olan ilk i indeksi, i + 1-in itən müsbət tam ədəd olduğunu göstərir.

3. Lazım gələrsə n + 1 qaytarın: Əgər 1-dən n-ə qədər bütün ədədlər düzgün mövqelərdədirsə, itən ədəd n + 1-dir.

Əsas Məqamlar:

• Yerdəyişmə yenidən düzəldilməsi: Əlavə yer istifadə etməmək üçün massivi özü dəyişdiririk.
• Effektivlik: Həm yenidən düzəldilmə, həm də son tarama $O(n)$ vaxt aparır, optimal performansı təmin edir.

2-ci Versiya: Performans Artımı (Artıq Yerdəyişmələrin Aradan Qaldırılması)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  // Ədədləri mümkün olduğu təqdirdə düzgün mövqelərinə yenidən düzün
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // Müvəqqəti dəyişən istifadə etmədən yerdəyişmə
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // İlk itən müsbəti müəyyən edin
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

İzah:

1. Effektiv Yenidən Düzəldilmə:

   • while dövrəsi elementləri birbaşa düzgün mövqelərinə (nums[idx] - 1) yalnız ədəd [1, n] aralığında və hələ də düzgün mövqedə deyilsə yerdəyişdirir.
   • if şərti qeyri-səhih və ya artıq düzgün ədədlərin lazımsız yerdəyişmələrsiz atılmasını təmin edir.

2. Birbaşa İndeks Yoxlaması:

   • Yenidən düzəldilmə mərhələsində, nums[idx]-in aralığını və qiymətini yoxlamaqla qeyri-səhih yerdəyişmələr və artıq əməliyyatlar qarşısı alınır.

3. Yaddaş-Effektiv Yerdəyişmə:

   • Dezstrukturlaşdırmanın istifadəsi ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) müvəqqəti dəyişənə ehtiyacı aradan qaldırır, yaddaş istifadəsini minimuma endirir.

4. Minimal Dövrələr:

   • Alqoritm yalnız iki xətti keçid istifadə edir:
     • Massivi yerində yenidən düzəltmək üçün biri.
     • İlk itən müsbəti tapmaq üçün digəri.

Mürəkkəblik Analizi:

• Vaxt Mürəkkəbliyi:
  • while dövrəsi və for dövrəsi hər ikisi $O(n)$ vaxtda işləyir, ümumi vaxt mürəkkəbliyini $O(n)$ edir.
• Yaddaş Mürəkkəbliyi:
  • Alqoritm əlavə köməkçi məlumat strukturlarından istifadə etmədən yerində işləyir, buna görə yaddaş mürəkkəbliyi $O(1)$-dir.

Niyə Bu Kod Optimaldir:

• Performans: Sadələşdirilmiş while dövrəsi minimal artıq əməliyyatları təmin edir, sürəti maksimuma çatdırır.
• Yaddaş Effektivliyi: Yerində yerdəyişmənin və əlavə dəyişənlərin qarşısının alınmasının istifadəsi mümkün olan ən aşağı yaddaş izini təmin edir.

3-cü Versiya: Yaddaş üçün Optimallaşdırılmış (Minimal Yaddaş İstifadəsi)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  while (idx < n) {
    const correctIdx = nums[idx] - 1

    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      nums[idx] = nums[correctIdx]
      nums[correctIdx] = correctIdx + 1
    } else {
      idx++
    }
  }

  for (let idx = 0; idx < n; idx++) {
    if (nums[idx] !== idx + 1) {
      return idx + 1
    }
  }

  return nums.length + 1
}

Əsas Yaddaş Optimallaşdırmaları:

1. Minimal Müvəqqəti Dəyişənlərlə Yerində Yeniləmələr:

   • Yerdəyişmə üçün temp dəyişənindən istifadə etmək əvəzinə, bu kod nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1 ilə massivi birbaşa dəyişdirir.
   • Bu, müvəqqəti dəyişənə ehtiyacı aradan qaldırır, yaddaş xərcini sabit miqdarda azaldır.

2. Dövrədə Daha Az Müvəqqəti Dəyər:

   • Kod correctIdx-i birbaşa dövrədə hesablayır, əsas məntiq xaricində əlavə ara dəyişənlərin saxlanmasına ehtiyacı aradan qaldırır.
   • Daha az dəyişən təyinatı hər iterasiya üçün biraz aşağı yaddaş istifadəsi deməkdir.

3. Yenidən Düzəldilmə üçün Tək Keçid:

   • while dövrəsində iç-içə şərti istifadə edən ilk koddan fərqli olaraq, bu tətbiq yerdəyişmələri tamamlayır və ya indeksi daha sadə bir şəkildə artırır, runtime yığınının dərinliyini və yaddaş istifadəsini azaldır.
   • Dövrə quruluşu (while tək artım və ya yenidən düzəldilmə ilə) daha birbaşa, daha az köməkçi dəyər tələb edir.

4. Artıq Yoxlamalar Yoxdur:

   • correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] üçün yoxlamalar qısadır və nəticəyə töhfə verməyən əməliyyatları qarşısını alır.
   • Bu, əməliyyatlar üçün əlavə resursların ayrılmasına ehtiyacı aradan qaldırır.

Niyə Bu Yaddaşda Fərq Yaradır:

• Azaldılmış Müvəqqəti Saxlama: temp dəyişənindən istifadə etməmək və ara hesablamaları minimuma endirməklə yaddaş izi daha kiçikdir.
• Sadələşdirilmiş İcra: Daha az addım və sadə məntiq hər əməliyyat üçün daha az yaddaş istifadəsi ilə nəticələnir.
• Yaxşılaşdırılmış Kəş Yaranması: Alqoritmin xətti, proqnozlaşdırıla bilən giriş nümunəsi CPU kəş performansını yaxşılaşdırır, dolayı yolla yaddaş xərcini azaldır.

Bu həllin birbaşa yerində yeniləmələrə, minimal dəyişən istifadəsinə və effektiv yaddaş giriş nümunələrinə diqqəti onu yaddaş effektivliyi baxımından ən yaxşısı edir. Qənaətlər sabit ($O(1)$) olsa da, xüsusilə böyük məlumat dəstləri üçün LeetCode kimi rəqabət platformalarında qeyd edilmək üçün kifayət qədər əhəmiyyətlidir.

4-cü Versiya: Optimallaşdırılmış Şah əsər (Yerdəyişmə, Müvəqqəti yoxdur)

function firstMissingPositive(nums: number[]): number {
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] !== i + 1) {
      if (nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]) {
        break
      }

      const temp = nums[i]
      nums[i] = nums[temp - 1]
      nums[temp - 1] = temp
    }
  }

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return nums.length + 1
}

Bu son versiya həm optimal performansı, həm də minimal yaddaş istifadəsini müvəqqəti dəyişən olmadan zərif yerində yerdəyişmə vasitəsilə əldə edir. Vaxt mürəkkəbliyi indi möhkəm $O(n)$-dir və yaddaş mürəkkəbliyi $O(1)$-dir, bütün tələbləri yerinə yetirir. Riyazi olaraq, elementləri "düzgün" mövqelərinə yerləşdirmək üçün massivin içərisində bir növ dövri permutasiya aparırıq.

nums[i] === nums[nums[i] - 1] yoxlaması əlavə etməklə lazımsız yerdəyişmələrin qarşısını alırıq. Bu, performansı əhəmiyyətli dərəcədə yaxşılaşdırır, vaxt mürəkkəbliyini istənilən $O(n)$-ə yaxınlaşdırır.

Tətbiqdə Əsas Fərqlər:

1. Artıq Yerdəyişmələrin Qarşısının Alınması:

   • Təqdim olunan kod yerdəyişməni yerinə yetirməzdən əvvəl nums[i] === nums[nums[i] - 1]-i açıq şəkildə yoxlayır. Bu, ədəd artıq düzgün mövqedə olduqda və ya kopyalar olduqda lazımsız yerdəyişmələrin qarşısını alır.
   • İlk tətbiqdə bu yoxlama buraxılıb, lazım olmadıqda belə artıq yerdəyişmələrə səbəb ola bilər. Hər əlavə yerdəyişmə xüsusilə böyük massivlər üçün əlavə yük əlavə edir.

2. Birbaşa İndeks Müqayisəsi:

   • Təqdim olunan kod ədədin təkrar-təkrar düzgün mövqeyinə yerdəyişdirilməsini və ya qeyri-səhih bir şərtə rast gəlinənə qədər while (nums[i] !== i + 1) istifadə edir. Bu, lazımsız dövrə iterasiyalarını aradan qaldırır.
   • İlk kod dövrə şərtində ədədin nəzərdə tutulan indeks ilə açıq şəkildə müqayisəsini etmir. Ədədlərin minimal hərəkətə ehtiyacı olduqda daha çox əməliyyat yerinə yetirə bilər.

3. Optimallaşdırılmış Şərti Yoxlamalar:

   • Şərti bir if blokunun içərisində birləşdirməklə (məs., nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), kod lazımsız yoxlamalardan və ya hesablamalardan əlavə yükü aradan qaldırır.

Niyə Bu LeetCode-da Əhəmiyyətlidir:

• Runtime Davamlılığı:

  • LeetCode-un runtime ölçmələri artıq yerdəyişmələr və ya əlavə müqayisələr kimi lazımsız əməliyyatlara həssas ola bilər.
  • Təqdim olunan kod bu əməliyyatları minimuma endirir, orta hesabla daha sürətli runtime ilə nəticələnir.

• Kəş Effektivliyi:

  • Daha az yerdəyişmə və sadə dövrə məntiqi daha yaxşı CPU kəş istifadəsinə səbəb olur. Müasir prosessorlar proqnozlaşdırıla bilən və sadələşdirilmiş giriş nümunələrindən faydalanır, təqdim olunan kod da bunu göstərir.

Nəticələr

Budur, cədvəl formatında təqdim olunan xülasə:

Bu cədvəl kompromisleri və son həllin optimallığını vurğulayır.

Xülasə göstərir ki, ən yaxşı performans və yaddaş üçün cəhd həqiqətən ən optimallaşdırılmışdır, əldə edir:

• 1 ms runtime: Performans baxımından ən sürətli nəticə ilə üst-üstə düşür.
• 58.9 MB yaddaş istifadəsi: "Ən yaxşı yaddaş" klonundan bir qədər yüksək, lakin digər cəhdlərdən aşağıdır.

Analiz:

1. Runtime:

   • 1 ms runtime optimallaşdırılmış yanaşmanın artıq yoxlamaları və lazımsız yerdəyişmələri aradan qaldırdığını göstərir.
   • $O(n)$ sabit vaxt mürəkkəbliyi daha böyük məlumat dəstləri üçün miqyaslanmanı təmin edir.

2. Yaddaş:

   • 58.9 MB rəqabət qabiliyyətlidir, sürətli icraya baxmayaraq yaddaş izinin aşağı olduğunu göstərir. "Ən yaxşı yaddaş" (58.5 MB) ilə bu kiçik artım dezstrukturlaşdırma və ya mühərrik-spesifik optimallaşdırmalardakı fərqlərdən qaynaqlana bilər.

3. Kompromisler:

   • "Ən yaxşı yaddaş" həlli daha aşağı yaddaş istifadəsi üçün runtime-dan bir qədər qurban verir.
   • "Ən yaxşı performans" həlli daha çox sürətə diqqət edir, lakin bir qədər çox yaddaş istifadə edir.

Nəticə:

Optimallaşdırılmış həll yaxşı balans yaradır:

• 1 ms runtime ən yaxşı performans göstərən kod qədər sürətlidir.
• 58.9 MB yaddaş istifadəsi ən yaxşı yaddaş nəticəsinə yaxındır, əhəmiyyətsiz əlavə yük ilə.

Həm performans, həm də yaddaşın vacib olduğu ssenarilər üçün yaxşı düşünülmüş seçimdir.

Riyazi Əsaslar: Dövri Permutasiyalar və Göyərçin Prinsipi

Əsas fikir dövri permutasiyalar anlayışı ətrafında fırlanır. Hər bir $x$ ədədinin $x - 1$ indeksində yerləşdirildiyi bir dövr yaratmağı hədəfləyirik. while dövrəsi bu dövrələri effektiv şəkildə gəzir, hər bir elementin təyin olunmuş yerini tapmasını təmin edir.

Göyərçin Prinsipi burada incə bir rol oynayır. $n$ mümkün mövqe ( $0$-dan $n-1$-ə qədər indekslər) olduğundan və $[1, n+1]$ aralığında itən müsbət tam ədəd axtarırıq, əgər 1-dən n-ə qədər bütün ədədlər varsa, itən ədəd $n + 1$ olmalıdır.

Həvəs Davam edir...

LeetCode 41-ə olan marağım qalmaqdadır. Davamlı olaraq daha da optimallaşdırmalar və daha dərin anlayışlar axtarıram. Bu axtarışa mənimlə qoşulun! Fikirlərinizi, öz həllərinizi paylaşın və riyaziyyat və alqoritmlərin zərif kəsişməsini birlikdə araşdıraq.