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

Небесно-голубой и розовый фон с логотипами C++, Python и JavaScript

Введение

Массив — это последовательная структура данных, где элементы одного типа хранятся в смежных ячейках памяти. Частые операции над массивами: вставка, удаление, поиск, обновление и обход.

Удаление дубликатов — частая задача на интервью и в реальных проектах. В этой статье мы разберём методы для неотсортированных и отсортированных массивов, объясним логические шаги и покажем код на трёх популярных языках.

Important: выбор метода зависит от свойств входных данных (отсортированы/неотсортированы), ограничений по памяти и требуемого порядка элементов.

Как удалить дубликаты из неотсортированного массива

Условие задачи

Дан неотсортированный массив целых чисел. Нужно вывести массив без повторяющихся элементов, сохранив порядок первого появления каждого уникального значения.

Примеры

Пример 1: arr = [23, 35, 23, 56, 67, 35, 35, 54, 76]
Результат: 23 35 56 67 54 76
Пример 2: arr = [5, 6, 1, 1, 7, 5, 8, 2, 7, 8]
Результат: 5 6 1 7 8 2

Подход

Хорошая и простая стратегия — пройти по массиву слева направо и хранить уже увиденные значения в структуре множества/хеш-таблице. При встрече нового элемента печатаем или добавляем его в выходную коллекцию, при встрече уже виденного — пропускаем.

Краткий алгоритм

Создать хеш-таблицу (set/map), чтобы отмечать увиденные элементы.
Пройти по входному массиву в порядке индексов.
Для каждого элемента проверить, есть ли он в хеше.
Если нет — добавить в результат и пометить в хеше.
Если есть — пропустить.

Временная сложность: O(n) при амортизированном доступе к хеш-таблице. Пространственная сложность: O(k), где k — число уникальных элементов.

C++: удаление дубликатов из неотсортированного массива

// C++ program to remove duplicate elements from an unsorted array
#include 
using namespace std;

// Function to remove duplicate elements from an unsorted array
void removeDuplicateElements(int arr[], int size)
{
    unordered_map m;

    for(int i=0; i

Вывод программы

Initial Array:
23 35 23 56 67 35 35 54 76
Array after removing duplicates:
23 35 56 67 54 76
Initial Array:
5 6 1 1 7 5 8 2 7 8
Array after removing duplicates:
5 6 1 7 8 2
Initial Array:
32 35 33 32 33 38 32 39
Array after removing duplicates:
32 35 33 38 39

`Python: удаление дубликатов из неотсортированного массива`

# Python program to remove duplicate elements from an unsorted list

def removeDuplicateElements(arr, size):
    m = {}

    for i in range(size):
        # Print the element if it's not
        # present in the dictionary
        if arr[i] not in m:
            print(arr[i], end = " ")
        # Insert the element in the dictionary
        m[arr[i]] = 1

    print()


def printListElements(arr, size):
    for i in range(size):
        print(arr[i], end=" ")
    print()

arr1 = [23, 35, 23, 56, 67, 35, 35, 54, 76]
size1 = len(arr1)
print("Initial List: ")
printListElements(arr1, size1)
print("List after removing duplicates: ")
removeDuplicateElements(arr1, size1)

arr2 = [5, 6, 1, 1, 7, 5, 8, 2, 7, 8]
size2 = len(arr2)
print("Initial List: ")
printListElements(arr2, size2)
print("List after removing duplicates: ")
removeDuplicateElements(arr2, size2)

arr3 = [32, 35, 33, 32, 33, 38, 32, 39]
size3 = len(arr3)
print("Initial List: ")
printListElements(arr3, size3)
print("List after removing duplicates: ")
removeDuplicateElements(arr3, size3)

Вывод

Initial Array:
23 35 23 56 67 35 35 54 76
Array after removing duplicates:
23 35 56 67 54 76
Initial Array:
5 6 1 1 7 5 8 2 7 8
Array after removing duplicates:
5 6 1 7 8 2
Initial Array:
32 35 33 32 33 38 32 39
Array after removing duplicates:
32 35 33 38 39

`JavaScript: удаление дубликатов из неотсортированного массива`

// JavaScript program to remove duplicate elements from an unsorted array

// Function to remove duplicate elements from an unsorted array
function removeDuplicateElements(arr, size) {
    let m = new Map();

    for (let i = 0; i < size; i++) {
        // Print the element if it's not
        // present in the hash map
        if (m.get(arr[i]) == null) {
            document.write(arr[i] + " ");
        }
        // Insert the element in the hash map
        m.set(arr[i], true);
    }
    document.write("
");
}

function printArrayElements(arr, size) {
    for(let i=0; i");
}

let arr1 = [23, 35, 23, 56, 67, 35, 35, 54, 76];
let size1 = arr1.length;
document.write("Initial Array: 
");
printArrayElements(arr1, size1);
document.write("Array after removing duplicates: 
");
removeDuplicateElements(arr1, size1);

let arr2 = [5, 6, 1, 1, 7, 5, 8, 2, 7, 8];
let size2 = arr2.length;
document.write("Initial Array: 
");
printArrayElements(arr2, size2);
document.write("Array after removing duplicates: 
");
removeDuplicateElements(arr2, size2);

let arr3 = [32, 35, 33, 32, 33, 38, 32, 39];
let size3 = arr3.length;
document.write("Initial Array: 
");
printArrayElements(arr3, size3);
document.write("Array after removing duplicates: 
");
removeDuplicateElements(arr3, size3);

Вывод в браузере (document.write)

Initial Array:
23 35 23 56 67 35 35 54 76
Array after removing duplicates:
23 35 56 67 54 76
Initial Array:
5 6 1 1 7 5 8 2 7 8
Array after removing duplicates:
5 6 1 7 8 2
Initial Array:
32 35 33 32 33 38 32 39
Array after removing duplicates:
32 35 33 38 39

`Как удалить дубликаты из отсортированного массива`

`Условие задачи`

Дан отсортированный массив целых чисел. Нужно удалить дубликаты и получить массив уникальных элементов. Поскольку массив отсортирован, одинаковые элементы идут подряд, это упрощает задачу.

Примеры

Пример 1: arr = [1, 1, 1, 2, 4, 6, 8, 8, 9, 9]
Результат: 1 2 4 6 8 9
Пример 2: arr = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
Результат: 1 2 3 4 5

`Подход`

Используем два указателя i и j:

i проходит по массиву для поиска границ последовательностей равных элементов.
j указывает позицию, куда нужно записать следующий уникальный элемент.
Когда arr[i] != arr[i+1], записываем arr[i] в arr[j] и увеличиваем j.
В конце — записываем последний элемент.
Возвращаем новую длину j.

Временная сложность: O(n). Пространственная: O(1) — алгоритм выполняется «на месте».

`C++: удаление дубликатов из отсортированного массива`

// C++ program to remove duplicate elements from a sorted array
#include 
using namespace std;

// Function to remove duplicate elements from a sorted array
int removeDuplicateElements(int arr[], int size)
{
    int j = 0;

    for (int i = 0; i < size-1; i++)
    {
        // If ith element is not equal to (i+1)th element,
        // then store ith value in arr[j]
        if (arr[i] != arr[i+1])
        {
            arr[j] = arr[i];
            j++;
        }
    }

    // Storing the last value of arr in arr[j]
    arr[j++] = arr[size-1];

    return j;
}

void printArrayElements(int arr[], int size)
{
    for(int i=0; i

Вывод

Initial Array:
1 1 1 2 4 6 8 8 9 9
Array after removing duplicates:
1 2 4 6 8 9
Initial Array:
1 1 2 2 3 3 4 4 5 5
Array after removing duplicates:
1 2 3 4 5
Initial Array:
10 12 12 14 16 16 18 19 19
Array after removing duplicates:
10 12 14 16 18 19

`Python: удаление дубликатов из отсортированного массива`

# Python program to remove duplicate elements from a sorted array

def removeDuplicateElements(arr, size):
    j = 0
    for i in range(size-1):
        if arr[i] != arr[i+1]:
            arr[j] = arr[i]
            j = j+1

    arr[j] = arr[size-1]
    j = j+1

    return j

def printListElements(arr, size):
    for i in range(size):
        print(arr[i], end=" ")
    print()

arr1 = [1, 1, 1, 2, 4, 6, 8, 8, 9, 9]
size1 = len(arr1)
print("Initial Array:")
printListElements(arr1, size1)
print("Array after removing duplicates:")
size1 = removeDuplicateElements(arr1, size1)
printListElements(arr1, size1)

arr2 = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
size2 = len(arr2)
print("Initial Array:")
printListElements(arr2, size2)
print("Array after removing duplicates:")
size2 = removeDuplicateElements(arr2, size2)
printListElements(arr2, size2)

arr3 = [10, 12, 12, 14, 16, 16, 18, 19, 19]
size3 = len(arr3)
print("Initial Array:")
printListElements(arr3, size3)
print("Array after removing duplicates:")
size3 = removeDuplicateElements(arr3, size3)
printListElements(arr3, size3)

`JavaScript: удаление дубликатов из отсортированного массива`

// JavaScript program to remove duplicate elements from a sorted array

// Function to remove duplicate elements from a sorted array
function removeDuplicateElements(arr, size)
{
    let j = 0;

    for (let i = 0; i < size-1; i++)
    {
        // If ith element is not equal to (i+1)th element,
        // then store ith value in arr[j]
        if (arr[i] != arr[i+1])
        {
            arr[j] = arr[i];
            j++;
        }
    }

    // Storing the last value of arr in arr[j]
    arr[j++] = arr[size-1];

    return j;
}

function printArrayElements(arr, size) {
    for(let i=0; i");
}

var arr1 = [1, 1, 1, 2, 4, 6, 8, 8, 9, 9];
var size1 = arr1.length;
document.write("Initial Array: 
");
printArrayElements(arr1, size1);
document.write("Array after removing duplicates: 
");
size1 = removeDuplicateElements(arr1, size1);
printArrayElements(arr1, size1);

var arr2 = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5];
var size2 = arr2.length;
document.write("Initial Array: 
");
printArrayElements(arr2, size2);
document.write("Array after removing duplicates: 
");
size2 = removeDuplicateElements(arr2, size2);
printArrayElements(arr2, size2);

var arr3 = [10, 12, 12, 14, 16, 16, 18, 19, 19];
var size3 = arr3.length;
document.write("Initial Array: 
");
printArrayElements(arr3, size3);
document.write("Array after removing duplicates: 
");
size3 = removeDuplicateElements(arr3, size3);
printArrayElements(arr3, size3);

Выводы для отсортированных массивов совпадают с примерами выше.

`Альтернативные подходы и рекомендации`

Сортировать + unique. Если порядок не важен, можно отсортировать массив O(n log n), затем пройти и убрать подряд идущие дубликаты. Это полезно, когда память ограничена, а сортировка допустима.
Использовать структуру «множество» (set) для быстрого удаления дубликатов, но при этом порядок теряется (в большинстве реализаций) или изменяется.
Для больших наборов данных, когда нельзя держать все в памяти, использовать потоковую обработку с внешним хешированием или сортировкой по частям (external sort).
Если значения — небольшие неотрицательные целые числа и диапазон известен, можно применять битовые массивы (bitset) для экономии памяти.

Когда этот метод не подойдёт

Если вход огромный и хеш-таблица не помещается в оперативной памяти.
Если требуется сохранять многократные вхождения по специальному правилу (например, разрешены ровно два вхождения).

`Практические советы для собеседований`

Поясните предположения: отсортирован ли массив? Требуется ли сохранять порядок?
Назовите временную и пространственную сложность выбранного подхода.
Если вы используете хеш-таблицу, упомяните амортизированную сложность операций.
Для «на месте» решения на отсортированном массиве объясните смысл двух указателей (i и j).

Краткий чек-лист для интервьюера

Объяснил ли кандидат алгоритм?
Верно ли указаны сложности?
Обработаны ли крайние случаи: пустой массив, все элементы одинаковы, все уникальны?
Написан ли корректный код и понятный вывод?

`Мини-методология: как подойти к задаче`

Спросить у интервьюера про ограничения и ожидаемый порядок.
Выбрать подход: хеш (память + порядок) / сортировка (меньше памяти) / два указателя (если отсортирован).
Указать сложность и граничные случаи.
Написать код и пройти тесты вручную на нескольких примерах.

`Тесты и критерии приёмки`

Примеры тест-кейсов, которые обязательно прогнать:

Пустой массив -> ожидаемый результат: пустой (ничего не печатать).
Массив из одного элемента -> тот же элемент.
Все элементы равны -> один элемент в результате.
Все элементы уникальны -> массив без изменений (для сохранения порядка).
Большой массив с повторяющимися блоками -> проверить корректность и производительность.

Критерии приёмки

Функция возвращает корректный набор уникальных элементов.
Если решение «на месте» — новые данные расположены в первых j ячейках.
Нет ошибок доступа по памяти и индексам.

`Решение выбора метода — наглядная схема`

flowchart TD
  A[Есть массив?] --> B{Массив отсортирован?}
  B -- Да --> C[Использовать два указателя 'in-place O'1' доп. памяти']
  B -- Нет --> D{Требуется сохранить порядок?}
  D -- Да --> E[Использовать хеш-множество 'O'n' память']
  D -- Нет --> F{Память ограничена?}
  F -- Да --> G[Отсортировать + пройти 'O'n log n', O'1' доп. памяти']
  F -- Нет --> E

`Заключение`

Удаление дубликатов — базовая задача, для которой есть простые и эффективные решения в зависимости от контекста. Для неотсортированных массивов чаще используют хеш-таблицы (O(n) время), для отсортированных — два указателя (O(n) время, O(1) память). При ограничениях по памяти стоит рассматривать сортировку или внешние алгоритмы.

Summary:

Для неотсортированных массивов: хеш-таблица — быстро и просто.
Для отсортированных массивов: два указателя — оптимально по памяти.
Если порядок не важен и память ограничена: сортировка + проход.

Если вы готовитесь к собеседованию, потренируйте оба подхода и прогоните тест-кейсы из раздела “Тесты и критерии приёмки”.

Раздел для практики: проверьте задачи на палиндромы, анаграммы, частоту символов, разворот массива и реализацию сортировок — это хорошие сопутствующие задачи для интервью.

Удаление дубликатов в массивах (отсортированных и неотсортированных)