Моя одержимость LeetCode 41: Глубокое погружение в головоломку с первым пропущенным положительным числом

Задача LeetCode "Первый пропущенный положительный" (номер 41) стала моей последней кодировочной одержимостью. Это обманчиво простая головоломка, которая завладела моими мыслями, побуждая меня исследовать её тонкости и создать максимально эффективное решение на TypeScript. Этот пост — не просто о сдаче собеседований по программированию (хотя это приятный бонус). Это о чистой радости решения задач, острых ощущениях от оптимизации и элегантной красоте эффективного кода. А поскольку я немного помешан на математике, мы даже углубимся в математические основы решения.

Задача: Волк в овечьей шкуре

Задача представляет собой несортированный массив целых чисел. Ваша задача: найти наименьшее пропущенное положительное целое число. Кажется простым? Подумайте ещё раз. Ограничения по времени $O(n)$ и пространству $O(1)$ превращают эту, казалось бы, простую задачу в сложную алгоритмическую головоломку.

Первоначальные трудности: Ловушка грубой силы

Мои первые попытки включали сортировку (нарушение ограничения по времени $O(n)$) и хэш-множества (превышение предела пространства $O(1)$). Очевидно, был нужен более сложный подход.

Момент озарения: Преобразование на месте

Ключевым моментом стало понимание того, что я могу использовать сам входной массив в качестве хэш-таблицы. Переставляя элементы, я могу поместить число $x$ в индекс $x - 1$ (если $1 \le x \le n$, где $n$ — длина массива). Это преобразование на месте открывает путь к эффективному решению.

Эволюция кода: Сага TypeScript

Вот хроника эволюции моего кода с подробными объяснениями и математическими выкладками:

Версия 1: Наивный подход (с избыточными обменами)

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

  // Поместите каждое число в его правильное положение, если оно находится в диапазоне [1, n]
  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]] // Обмен
    }
  }

  // Найдите первое пропущенное положительное число
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Если все числа находятся в своих правильных позициях, пропущенное число равно n + 1
  return n + 1
}

Эта версия, хотя и функциональна, страдает от избыточных обменов. Количество обменов в худшем случае приближается к $O(n^2)$, хотя в среднем случае оно ближе к $O(n)$.

Объяснение:

1. Перестановка массива: Каждое число nums[i] помещается в свой "правильный" индекс (nums[i] - 1), если оно находится в диапазоне [1, n] и ещё не находится в правильном положении.

2. Идентификация пропущенного положительного числа: После перестановки первый индекс i, где nums[i] !== i + 1, указывает на то, что i + 1 — это пропущенное положительное целое число.

3. Возврат n + 1 при необходимости: Если все числа от 1 до n находятся в правильных позициях, пропущенное число равно n + 1.

Ключевые моменты:

• Перестановка на месте: Мы изменяем сам массив, чтобы избежать использования дополнительного пространства.
• Эффективность: И перестановка, и окончательное сканирование занимают время $O(n)$, обеспечивая оптимальную производительность.

Версия 2: Увеличение производительности (исключение избыточных обменов)

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], nums[idx]]
    } else {
      idx++
    }
  }

  // Определите первое пропущенное положительное число
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

Объяснение:

1. Эффективная перестановка:

   • Цикл while переставляет элементы непосредственно в их правильные позиции (nums[idx] - 1) только тогда, когда число находится в допустимом диапазоне [1, n] и ещё не находится в правильном положении.
   • Условие if гарантирует, что недопустимые или уже правильные числа пропускаются без лишних обменов.

2. Прямая проверка индекса:

   • На этапе перестановки недопустимые обмены и избыточные операции избегаются за счёт проверки диапазона и значения nums[idx].

3. Обмен, эффективный по памяти:

   • Использование деструктуризации ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) исключает необходимость во временной переменной, минимизируя использование памяти.

4. Минимальное количество циклов:

   • Алгоритм использует только два линейных прохода:
     • Один для перестановки массива на месте.
     • Другой для поиска первого пропущенного положительного числа.

Анализ сложности:

• Временная сложность:
  • Цикл while и цикл for выполняются за $O(n)$, что делает общую временную сложность $O(n)$.
• Пространственная сложность:
  • Алгоритм работает на месте, не используя никаких вспомогательных структур данных, поэтому пространственная сложность составляет $O(1)$.

Почему этот код оптимален:

• Производительность: Упрощённый цикл while обеспечивает минимальное количество избыточных операций, максимизируя скорость.
• Эффективность памяти: Использование перестановки на месте и избегание дополнительных переменных обеспечивает минимальное возможное потребление памяти.

Версия 3: Оптимизированная для памяти (минимальное использование памяти)

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
}

Ключевые оптимизации памяти:

1. Обновления на месте с минимальным количеством временных переменных:

   • Вместо использования переменной temp для обмена этот код напрямую изменяет массив с помощью nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1.
   • Это исключает необходимость во временной переменной, уменьшая накладные расходы на память на постоянную величину.

2. Меньше временных значений в цикле:

   • Код вычисляет correctIdx непосредственно в цикле, избегая необходимости хранить дополнительные промежуточные переменные вне основной логики.
   • Меньшее количество присваиваний переменных означает немного меньшее потребление памяти на каждой итерации.

3. Единичный проход для перестановки:

   • В отличие от первого кода, который использует вложенные условия в цикле while, эта реализация завершает обмены или продвигает индекс более упорядоченным образом, уменьшая глубину стека времени выполнения и потребление памяти.
   • Структура цикла (while с одним увеличением или перестановкой) более прямая, требующая меньшего количества вспомогательных значений.

4. Отсутствие избыточных проверок:

   • Проверки correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] лаконичны и предотвращают ненужные операции, которые могли бы временно использовать память стека или кэш процессора.
   • Это позволяет избежать необходимости выделения дополнительных ресурсов для операций, которые не будут способствовать результату.

Почему это имеет значение для памяти:

• Уменьшенное временное хранилище: Избегая использования переменной temp и минимизируя промежуточные вычисления, уменьшается занимаемая память.
• Упрощённое выполнение: Меньшее количество шагов и более простая логика приводят к меньшему использованию памяти на каждую операцию.
• Улучшенное использование кэша: Линейная, предсказуемая схема доступа алгоритма улучшает производительность кэша процессора, косвенно уменьшая накладные расходы на память.

Этот подход, ориентированный на прямые обновления на месте, минимальное использование переменных и эффективные схемы доступа к памяти, является лучшим с точки зрения эффективности использования памяти. Хотя экономия постоянна ($O(1)$), она достаточно значительна, чтобы регистрироваться на конкурентных платформах, таких как LeetCode, особенно для больших наборов данных.

Версия 4: Оптимизированный шедевр (обмен на месте, без временной переменной)

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
}

Эта окончательная версия достигает как оптимальной производительности, так и минимального использования памяти за счёт элегантного обмена на месте без временной переменной. Временная сложность теперь твёрдо $O(n)$, а пространственная сложность $O(1)$, что удовлетворяет всем требованиям. С математической точки зрения, мы выполняем своего рода циклическую перестановку внутри массива, чтобы поместить элементы в их "правильные" позиции.

Добавив проверку (nums[i] === nums[nums[i] - 1]), мы предотвращаем ненужные обмены. Это значительно улучшает производительность, приближая временную сложность к желаемой $O(n)$.

Ключевые отличия в реализации:

1. Избегание избыточных обменов:

   • Предоставленный код явно проверяет, является ли nums[i] === nums[nums[i] - 1] перед выполнением обмена. Это позволяет избежать ненужных обменов, когда число уже находится в правильном положении или существуют дубликаты.
   • В первой реализации эта проверка опущена, что может привести к избыточным обменам даже когда они не нужны. Каждый дополнительный обмен добавляет накладные расходы, особенно для больших массивов.

2. Прямое сравнение индексов:

   • Предоставленный код использует while (nums[i] !== i + 1), чтобы гарантировать, что число неоднократно переставляется в свою правильную позицию, пока оно не будет правильно размещено или не будет выполнено недопустимое условие. Это исключает ненужные итерации цикла.
   • Первый код не сравнивает явно число с его предполагаемым индексом в условии цикла. Он может выполнять больше операций в случаях, когда числа требуют минимального перемещения.

3. Оптимизированные условные проверки:

   • Объединяя условия в одном блоке if (например, nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), код избегает дополнительных накладных расходов от ненужных проверок или вычислений.

Почему это имеет значение в LeetCode:

• Согласованность времени выполнения:

  • Измерения времени выполнения LeetCode могут быть чувствительны к ненужным операциям, таким как избыточные обмены или дополнительные сравнения.
  • Предоставленный код сводит к минимуму эти операции, что приводит к более быстрому времени выполнения в среднем.

• Эффективность кэша:

  • Меньшее количество обменов и более простая логика цикла приводят к лучшему использованию кэша процессора. Современные процессоры выигрывают от предсказуемых и упорядоченных схем доступа, которые демонстрирует предоставленный код.

Результаты

Вот сводка, представленная в табличном формате:

Эта таблица выделяет компромиссы и оптимальность окончательного решения.

Резюме показывает, что попытка с лучшей производительностью и памятью действительно является наиболее оптимизированной, достигая:

• Время выполнения 1 мс: Соответствует самому быстрому результату с точки зрения производительности.
• Потребление памяти 58,9 МБ: Немного выше, чем у варианта "лучшая память" (58,5 МБ), но ниже, чем у других попыток.

Анализ:

1. Время выполнения:

   • Время выполнения 1 мс показывает, что оптимизированный подход исключает избыточные проверки и ненужные обмены.
   • Постоянная временная сложность $O(n)$ обеспечивает масштабируемость для больших наборов данных.

2. Память:

   • 58,9 МБ — конкурентоспособный показатель, демонстрирующий, что занимаемая память мала, несмотря на быстрое выполнение. Это небольшое увеличение по сравнению с "лучшей памятью" (58,5 МБ) может быть связано с различиями в деструктуризации или специфичными для движка оптимизациями.

3. Компромиссы:

   • Решение "лучшая память" немного жертвует временем выполнения ради меньшего потребления памяти.
   • Решение "лучшая производительность" больше ориентировано на скорость, но использует немного больше памяти.

Заключение:

Оптимизированное решение находит хороший баланс:

• Время выполнения 1 мс такое же быстрое, как у лучшего кода по производительности.
• Потребление памяти 58,9 МБ близко к результату "лучшей памяти" с незначительными накладными расходами.

Это сбалансированный выбор, особенно для сценариев, где важны как производительность, так и память.

Математические основы: Циклические перестановки и принцип Дирихле

Основная идея вращается вокруг концепции циклических перестановок. Мы стремимся создать цикл, где каждое число $x$ размещается в индексе $x - 1$. Цикл while эффективно проходит по этим циклам, гарантируя, что каждый элемент найдёт своё назначенное место.

Принцип Дирихле тонко играет здесь свою роль. Поскольку у нас есть $n$ возможных позиций (индексы от $0$ до $n-1$) и мы ищем пропущенное положительное целое число в диапазоне $[1, n+1]$, если присутствуют все числа от 1 до $n$, пропущенное число должно быть $n + 1$.

Одержимость продолжается...

Моя увлеченность задачей LeetCode 41 остаётся. Я постоянно ищу дальнейшие оптимизации и более глубокое понимание. Присоединяйтесь ко мне в этом поиске! Поделитесь своими мыслями, своими решениями, и давайте вместе исследуем элегантное пересечение математики и алгоритмов.