Удаление дубликатов из массива

Решение

Анализ задачи

Задача требует удалить дубликаты из массива, сохраняя исходный порядок элементов. Это важное уточнение — существует несколько подходов в зависимости от требований:

1. Простой подход — использовать хеш-множество (Set)
2. Подход с двумя указателями — для отсортированного массива
3. Встроенные функции — если язык их предоставляет

Мы рассмотрим все три, так как на собеседовании ценится понимание trade-offs.

Решение 1: Использование Set (Python)

def removeDuplicates(arr: list[int]) -> list[int]:
    """
    Удаляет дубликаты, сохраняя порядок через dict (3.7+).
    
    Сложность: O(n) время, O(n) память
    """
    # dict.fromkeys() сохраняет порядок в Python 3.7+
    return list(dict.fromkeys(arr))

Этот подход:

• Сохраняет порядок в Python 3.7+ (dict упорядочен)
• Линейная сложность O(n)
• Простота кода

Решение 2: Явное использование множества

def removeDuplicates(arr: list[int]) -> list[int]:
    """
    Удаляет дубликаты с явной проверкой через set.
    """
    seen = set()
    result = []
    
    for num in arr:
        if num not in seen:
            seen.add(num)
            result.append(num)
    
    return result

Преимущества:

• Явная логика — понятна на собеседовании
• Работает в любой версии Python
• Полный контроль над процессом
• Сложность: O(n) время, O(n) память

Решение 3: Java реализация

public class Solution {
    public static List<Integer> removeDuplicates(int[] arr) {
        // Используем LinkedHashSet для сохранения порядка
        Set<Integer> seen = new LinkedHashSet<>(Arrays.asList(
            Arrays.stream(arr).boxed().toArray(Integer[]::new)
        ));
        return new ArrayList<>(seen);
    }
}

Альтернатива (более явная):

public class Solution {
    public static List<Integer> removeDuplicates(int[] arr) {
        Set<Integer> seen = new LinkedHashSet<>();
        List<Integer> result = new ArrayList<>();
        
        for (int num : arr) {
            if (seen.add(num)) {  // add() возвращает false если элемент уже был
                result.add(num);
            }
        }
        
        return result;
    }
}

Решение 4: JavaScript/TypeScript

function removeDuplicates(arr) {
    // Используем Set для уникальности
    // Set в JavaScript сохраняет порядок вставки
    return [...new Set(arr)];
}

// С типизацией (TypeScript)
function removeDuplicates(arr: number[]): number[] {
    return [...new Set(arr)];
}

Решение 5: Для отсортированного массива (2 указателя)

Если массив отсортирован, можно использовать две указатели:

def removeDuplicates(arr: list[int]) -> list[int]:
    """
    Удаляет дубликаты в отсортированном массиве на месте.
    Возвращает новый массив (или можно изменять исходный).
    
    Сложность: O(n) время, O(1) дополнительная память
    """
    if not arr:
        return arr
    
    write_pos = 0
    
    for read_pos in range(1, len(arr)):
        if arr[read_pos] != arr[write_pos]:
            write_pos += 1
            arr[write_pos] = arr[read_pos]
    
    return arr[:write_pos + 1]

Сравнение подходов

Тестовые случаи

# Основной пример
assert removeDuplicates([1, 2, 2, 3, 4, 4, 5]) == [1, 2, 3, 4, 5]

# Граничные случаи
assert removeDuplicates([]) == []  # Пустой массив
assert removeDuplicates([1]) == [1]  # Один элемент
assert removeDuplicates([1, 1, 1, 1]) == [1]  # Все дубликаты
assert removeDuplicates([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5]  # Нет дубликатов

# Сохранение порядка
assert removeDuplicates([5, 2, 5, 3, 2, 1]) == [5, 2, 3, 1]  # Порядок первого появления

Рекомендация для QA

При тестировании:

• Пустой массив — должен вернуть пустой массив
• Нет дубликатов — массив не должен измениться
• Все дубликаты — должна остаться одна копия
• Смешанные данные — проверить сохранение порядка первого появления
• Большие массивы — проверить производительность
• Отрицательные числа — если применимо

Выбор подхода зависит от контекста — для собеседования рекомендую Решение 2 (явное использование set): оно показывает понимание алгоритма и работает везде.