Удалить дубликаты из отсортированного слайса

Удалить дубликаты из отсортированного слайса - полное решение

Описание задачи

Необходимо удалить дубликаты из отсортированного слайса на месте (in-place), то есть без создания нового слайса. Это классическая задача на двухпоказательную технику (two-pointers), где требуется O(1) дополнительной памяти.

Архитектурное решение

Используем two-pointers подход:

• slow pointer - указывает на позицию, где должен быть следующий уникальный элемент
• fast pointer - итерирует через весь слайс
• Когда найден новый элемент, перемещаем его на позицию slow pointer
• Возвращаем индекс slow pointer + 1 (количество уникальных элементов)

Реализация

package main

import "fmt"

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    slow := 0 // Указатель на позицию для уникального элемента
    
    // fast итерирует через весь слайс
    for fast := 1; fast < len(nums); fast++ {
        // Если найден новый элемент (отличается от предыдущего)
        if nums[fast] != nums[slow] {
            slow++
            nums[slow] = nums[fast]
        }
    }
    
    return slow + 1 // Количество уникальных элементов
}

func main() {
    testCases := []struct {
        input    []int
        expected int
    }{
        {[]int{1, 1, 2, 2, 2, 3, 4, 4, 5}, 5},
        {[]int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}, 5},
        {[]int{1}, 1},
        {[]int{}, 0},
        {[]int{1, 1, 1, 1}, 1},
        {[]int{1, 2, 3, 4, 5}, 5},
    }
    
    for i, tc := range testCases {
        nums := make([]int, len(tc.input))
        copy(nums, tc.input)
        
        result := removeDuplicates(nums)
        
        status := "✓"
        if result != tc.expected {
            status = "✗"
        }
        
        fmt.Printf("%s Test %d: got %d (expected %d)\\n", status, i+1, result, tc.expected)
        fmt.Printf("  Слайс: %v\\n", nums[:result])
    }
}

Анализ работы на примере

Дано: [1, 1, 2, 2, 2, 3, 4, 4, 5]

Шаг 1: slow=0, fast=1
  nums[1]=1 == nums[0]=1 → fast++

Шаг 2: slow=0, fast=2
  nums[2]=2 != nums[0]=1 → slow++, nums[1]=2
  Состояние: [1, 2, 1, 2, 2, 3, 4, 4, 5]

Шаг 3: slow=1, fast=3
  nums[3]=2 == nums[1]=2 → fast++

Шаг 4: slow=1, fast=4
  nums[4]=2 == nums[1]=2 → fast++

Шаг 5: slow=1, fast=5
  nums[5]=3 != nums[1]=2 → slow++, nums[2]=3
  Состояние: [1, 2, 3, 2, 2, 3, 4, 4, 5]

Шаг 6: slow=2, fast=6
  nums[6]=4 != nums[2]=3 → slow++, nums[3]=4
  Состояние: [1, 2, 3, 4, 2, 3, 4, 4, 5]

Шаг 7: slow=3, fast=7
  nums[7]=4 == nums[3]=4 → fast++

Шаг 8: slow=3, fast=8
  nums[8]=5 != nums[3]=4 → slow++, nums[4]=5
  Состояние: [1, 2, 3, 4, 5, 3, 4, 4, 5]

Возвращаем: slow + 1 = 5
Уникальные элементы: nums[0:5] = [1, 2, 3, 4, 5]

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

• Time: O(n) - один проход через слайс (два указателя)
• Space: O(1) - используем только два целых числа для указателей, не создаем новые структуры

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

1. Two-pointers техника - эффективный способ для работы с отсортированными данными
2. In-place модификация - записываем уникальные элементы в начало слайса
3. Соответствие требованиям памяти - используем только O(1) дополнительной памяти
4. Сохранение порядка - уникальные элементы остаются в исходном порядке

Граничные случаи

• Пустой слайс - возвращаем 0
• Один элемент - возвращаем 1
• Все элементы одинаковы - возвращаем 1
• Нет дубликатов - возвращаем исходную длину
• Все разные - массив остается неизменным

Почему два указателя работают?

Поскольку слайс отсортирован, все дубликаты идут подряд. Это позволяет нам:

• Пропускать дубликаты простым сравнением nums[fast] != nums[slow]
• Гарантировать, что после fast pointer нет нужных нам элементов
• Эффективно перемещать уникальные элементы в начало