Удаление дубликатов в массивах — примеры и код на C++, Python, JavaScript
Что такое массив и зачем удалять дубликаты
Массив — это линейная структура данных, элементы которой занимают смежные участки памяти и имеют одинаковый тип. Дубликаты в массивах часто мешают при подсчётах, агрегации и поиске уникальных значений (например, при построении множества пользователей или наборов тегов). В этой статье показаны простые и надёжные подходы для отсортированных и неотсортированных массивов, с рабочими примерами кода.
Основные варианты методов
- Быстро и просто для неотсортированного массива: использовать хеш-таблицу или Set.
- Если массив отсортирован: пройти один раз двумя индексами и перезаписать уникальные элементы на место.
- Если необходимо сохранить исходный порядок — применять структуру, сохраняющую порядок первой встречи (например, OrderedDict в Python, Map в JavaScript, или в C++ вектор + unordered_set с проверкой наличия).
Факт-бокс
- Сложность по времени для хеш-метода: O(n).
- Дополнительная память для хеш-метода: O(n) в худшем случае.
- Сложность по времени для метода для отсортированного массива: O(n).
- Дополнительная память для метода в отсортированном массиве: O(1) (in-place).
Как удалять дубликаты в неотсортированном массиве
Задача
Дан неотсортированный массив целых чисел. Нужно удалить повторяющиеся элементы и вывести массив уникальных значений в порядке их первого появления.
Примеры
- Пример 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), которая будет хранить уже встреченные элементы.
- Пройти по массиву слева направо.
- Для каждого элемента проверить, встречался ли он ранее.
- Если не встречался — вывести/добавить в результат и пометить в хеш-таблице.
- Если встречался — пропустить.
Этот метод сохраняет порядок первой встречи и работает за O(n) времени.
C++ пример для неотсортированного массива
// C++ program to remove duplicate elements from an unsorted array
#include
using namespace std;
// Функция для удаления дубликатов из неотсортированного массива
void removeDuplicateElements(int arr[], int size)
{
unordered_map m;
for(int i = 0; i < size; i++)
{
// Выводим элемент, если он ещё не встретился
if (m.find(arr[i]) == m.end())
{
cout << arr[i] << " ";
}
// Отмечаем элемент как встреченный
m[arr[i]] = true;
}
cout << endl;
}
void printArrayElements(int arr[], int size)
{
for(int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
int main()
{
int arr1[] = {23, 35, 23, 56, 67, 35, 35, 54, 76};
int size1 = sizeof(arr1)/sizeof(arr1[0]);
cout << "Initial Array: " << endl;
printArrayElements(arr1, size1);
cout << "Array after removing duplicates: " << endl;
removeDuplicateElements(arr1, size1);
int arr2[] = {5, 6, 1, 1, 7, 5, 8, 2, 7, 8};
int size2 = sizeof(arr2)/sizeof(arr2[0]);
cout << "Initial Array: " << endl;
printArrayElements(arr2, size2);
cout << "Array after removing duplicates: " << endl;
removeDuplicateElements(arr2, size2);
int arr3[] = {32, 35, 33, 32, 33, 38, 32, 39};
int size3 = sizeof(arr3)/sizeof(arr3[0]);
cout << "Initial Array: " << endl;
printArrayElements(arr3, size3);
cout << "Array after removing duplicates: " << endl;
removeDuplicateElements(arr3, size3);
return 0;
} Вывод программы (локализованный):
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 39Python пример для неотсортированного массива
# Python program to remove duplicate elements from an unsorted list
def removeDuplicateElements(arr, size):
m = {}
for i in range(size):
# Выводим элемент, если его нет в словаре
if arr[i] not in m:
print(arr[i], end = " ")
# Отмечаем элемент в словаре
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)Вывод программы показан выше в разделе C++.
JavaScript пример для неотсортированного массива
// JavaScript program to remove duplicate elements from an unsorted array
// Функция для удаления дубликатов
function removeDuplicateElements(arr, size) {
let m = new Map();
for (let i = 0; i < size; i++) {
// Выводим элемент, если он ещё не в Map
if (m.get(arr[i]) == null) {
document.write(arr[i] + " ");
}
// Отмечаем элемент
m.set(arr[i], true);
}
document.write("
");
}
function printArrayElements(arr, size) {
for(let i = 0; i < size; i++) {
document.write(arr[i] + " ");
}
document.write("
");
}
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);
// другие примеры аналогичноКак удалять дубликаты в отсортированном массиве
Задача
Дан отсортированный массив целых чисел. Нужно удалить дубликаты и вернуть новую длину массива (уникальные элементы будут в начале массива).
Примеры
- Пример 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.
- После завершения цикла записать последний элемент arr[size-1] в arr[j].
- Возвратить j — новую длину, уникальные элементы располагаются в arr[0..j-1].
Этот метод in-place экономит память и работает за O(n).
C++ пример для отсортированного массива
// C++ program to remove duplicate elements from a sorted array
#include
using namespace std;
// Функция для удаления дубликатов из отсортированного массива
int removeDuplicateElements(int arr[], int size)
{
int j = 0;
for (int i = 0; i < size - 1; i++)
{
// Если элемент не равен следующему, записываем его
if (arr[i] != arr[i + 1])
{
arr[j] = arr[i];
j++;
}
}
// Записываем последний элемент
arr[j++] = arr[size - 1];
return j;
}
void printArrayElements(int arr[], int size)
{
for(int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
int main()
{
int arr1[] = {1, 1, 1, 2, 4, 6, 8, 8, 9, 9};
int size1 = sizeof(arr1)/sizeof(arr1[0]);
cout << "Initial Array: " << endl;
printArrayElements(arr1, size1);
cout << "Array after removing duplicates: " << endl;
size1 = removeDuplicateElements(arr1, size1);
printArrayElements(arr1, size1);
int arr2[] = {1, 1, 2, 2, 3, 3, 4, 4, 5, 5};
int size2 = sizeof(arr2)/sizeof(arr2[0]);
cout << "Initial Array: " << endl;
printArrayElements(arr2, size2);
cout << "Array after removing duplicates: " << endl;
size2 = removeDuplicateElements(arr2, size2);
printArrayElements(arr2, size2);
int arr3[] = {10, 12, 12, 14, 16, 16, 18, 19, 19};
int size3 = sizeof(arr3)/sizeof(arr3[0]);
cout << "Initial Array: " << endl;
printArrayElements(arr3, size3);
cout << "Array after removing duplicates: " << endl;
size3 = removeDuplicateElements(arr3, size3);
printArrayElements(arr3, size3);
return 0;
} Вывод примера для отсортированного массива:
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 19Python и JavaScript для отсортированного массива
Код-логика в Python и JavaScript аналогична: один проход, два индекса, запись уникальных значений на место. В Python это работает с списком; в JavaScript — с массивом.
Когда предложенные методы не подходят
- Если память строго ограничена, но массив не отсортирован, in-place удаления без предварительной сортировки или внешних структур данных не даст ожидаемой эффективности.
- Если нужно удалить дубликаты по составному ключу (например, объект с несколькими полями), необходимо сравнение по ключу или генерация хеша по нужным полям.
- Для очень больших потоков данных, которые не помещаются в память, потребуется внешняя сортировка или MapReduce-подход.
Альтернативные подходы и варианты
- Сортировка + проход: отсортировать O(n log n), затем один проход O(n) с O(1) доп. памяти. Полезно, если O(n log n) допустимо и важно in-place.
- Использовать структуры, сохраняющие порядок: в Python — OrderedDict.fromkeys(arr) или list(dict.fromkeys(arr)) (Python 3.7+ dict сохраняет порядок), в JavaScript — […new Set(arr)] (но Set в JS сохраняет порядок вставки), в C++ можно собирать результат в вектор, проверяя unordered_set.
- Для потоковых данных применять скользящее окно или probabilistic структуры (Bloom filter) для экономии памяти с допущением ложных совпадений.
Стратегия выбора метода (решающее дерево)
flowchart TD
A[Массив отсортирован?] -->|Да| B[Использовать метод двух индексов 'in-place']
A -->|Нет| C[Нужно сохранить порядок?]
C -->|Да| D[Использовать хеш-таблицу/Set и сохранять порядок первой встречи]
C -->|Нет| E[Можно сортировать и затем удалить дубликаты]
D --> F[O'n' время, O'n' память]
B --> G[O'n' время, O'1' память]
E --> H[O'n log n' время, O'1' память]Чеклист для интервью
- Уточните, отсортирован массив или нет.
- Уточните требования к порядку элементов в результате.
- Обсудите ограничения по памяти и времени.
- Предложите in-place вариант для отсортированных данных и хеш-вариант для неотсортированных.
- Приведите примеры входных данных, включая крайние случаи (пустой массив, все элементы одинаковые, все уникальные).
Примеры крайних случаев и тесты приёмки
Критерии приёмки:
- Пустой массив возвращает пустой результат.
- Массив из одного элемента возвращает тот же элемент.
- Массив, где все элементы одинаковы, возвращает один элемент.
- Массив, где все элементы уникальны, возвращает исходный массив (сохранённый порядок при необходимости).
Минимальные тесты:
- [] → []
- [1] → [1]
- [2,2,2,2] → [2]
- [3,1,2,3,2,1] → [3,1,2] (для неотсортированного, порядок первой встречи)
- [1,1,2,2,3,3] → [1,2,3] (для отсортированного in-place)
Глоссарий в одну строку
- Массив: упорядоченная коллекция одинаковых по типу элементов.
- Хеш-таблица: структура данных для проверки наличия элемента за ожидаемое O(1).
- Set: коллекция уникальных значений.
- In-place: изменение структуры без существенной дополнительной памяти.
Рекомендации по производительности и безопасности
- Для целых чисел используйте unordered_set/unordered_map в C++ и Set в JavaScript для быстрого поиска.
- Для больших объектов храните и сравнивайте только ключи (идентификаторы), а не полные объекты.
- При многопоточном доступе к общей структуре используйте блокировки или потокобезопасные коллекции.
Часто задаваемые вопросы
Какова лучшая стратегия, если нужно удалить дубликаты и сохранить порядок вставки?
Используйте хеш-структуру, которая запоминает порядок (в современных Python dict и set сохраняют порядок вставки; в JavaScript Set сохраняет порядок). В C++ можно сочетать unordered_set для проверки и vector для хранения результатов в порядке первичных встреч.
Можно ли удалить дубликаты для очень большого массива, не помещающегося в память?
Требуется внешняя обработка: разбиение на чанки, сортировка чанков на диске и последующая внешняя сортировка/слияние, либо MapReduce-подход.
Итог
- Для неотсортированных массивов простой и эффективный метод — проход с хеш-структурой (O(n) времени, O(n) памяти), который сохраняет порядок первой встречи.
- Для отсортированных массивов наиболее экономичен метод двух индексов, работающий in-place (O(n) времени, O(1) памяти).
- Всегда уточняйте требования к порядку, ограничения по памяти и допустимую сложность времени, прежде чем предлагать окончательное решение.
Похожее: Как вывести “Hello, World!” в самых популярных языках программирования
Автор
Редакция
Похожие материалы
3D моделирование
Как разделить меш в Blender
Фото
Как увеличить изображение без потери качества
Видео
Как создать влог на iPhone — полное руководство
Руководство
Как отразить экран на телевизор — все способы
Vue
Бесконечная прокрутка в Vue 3 — useInfiniteScroll
iPhone