Эффективное удаление дубликатов из Java-массивов

Эффективное удаление дубликатов из массива является фундаментальной задачей в программировании. В этой статье рассматриваются три различных подхода на Java, каждый из которых предлагает различный баланс между скоростью и использованием памяти. Понимание этих компромиссов имеет решающее значение для выбора оптимального метода для вашего конкретного приложения.

Содержание

• Использование временного массива
• Использование отдельного индекса
• Использование метода Arrays.sort()
• Сравнение методов

Использование временного массива

Этот простой метод итерирует входной массив. Каждый элемент проверяется на наличие в временном массиве, содержащем только уникальные элементы, встреченные до сих пор. Если элемент не найден во временном массиве, он добавляется. Несмотря на простоту понимания, его структура с вложенными циклами приводит к временной сложности O(n²), что делает его неэффективным для больших массивов.

import java.util.Arrays;

public class RemoveDuplicates {

    public static int[] removeDuplicatesTempArray(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0]; 
        }

        int[] uniqueArr = new int[arr.length]; 
        int uniqueCount = 0;

        for (int i = 0; i < arr.length; i++) {
            boolean isDuplicate = false;
            for (int j = 0; j < uniqueCount; j++) {
                if (arr[i] == uniqueArr[j]) {
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {
                uniqueArr[uniqueCount++] = arr[i];
            }
        }

        return Arrays.copyOf(uniqueArr, uniqueCount); 
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 4, 4, 5, 5, 5};
        int[] uniqueArr = removeDuplicatesTempArray(arr);
        System.out.println("Исходный массив: " + Arrays.toString(arr));
        System.out.println("Массив без дубликатов: " + Arrays.toString(uniqueArr));
    }
}

Временная сложность: O(n²)
Пространственная сложность: O(n)

Использование отдельного индекса

Этот метод повышает эффективность использования памяти за счет модификации исходного массива на месте. Он использует отдельный индекс для отслеживания позиции следующего уникального элемента. Массив итерируется, и уникальные элементы перемещаются в позиции, указанные этим индексом. Несмотря на эффективное использование памяти (O(1)), он по-прежнему страдает от временной сложности O(n²) из-за вложенных циклов.

public class RemoveDuplicates {

    public static int[] removeDuplicatesIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        int index = 1; 
        for (int i = 1; i < arr.length; i++) {
            boolean isDuplicate = false;
            for (int j = 0; j < index; j++) {
                if (arr[i] == arr[j]) {
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {
                arr[index++] = arr[i];
            }
        }
        return Arrays.copyOf(arr, index);
    }
    //метод main остается таким же, как и выше
}

Временная сложность: O(n²)
Пространственная сложность: O(1)

Использование метода Arrays.sort()

Этот подход использует встроенную функциональность сортировки Java. Сортировка массива сначала объединяет дубликаты. Последующий единственный проход по отсортированному массиву идентифицирует и сохраняет только первое вхождение каждого элемента. Временная сложность определяется алгоритмом сортировки (O(n log n)), что обеспечивает значительно лучшие показатели производительности для больших наборов данных, чем предыдущие методы.

import java.util.Arrays;

public class RemoveDuplicates {

    public static int[] removeDuplicatesSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        Arrays.sort(arr); 
        int[] uniqueArr = new int[arr.length];
        uniqueArr[0] = arr[0]; 
        int uniqueCount = 1;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[i - 1]) {
                uniqueArr[uniqueCount++] = arr[i];
            }
        }

        return Arrays.copyOf(uniqueArr, uniqueCount);
    }
    //метод main остается таким же, как и выше
}

Временная сложность: O(n log n)
Пространственная сложность: O(n)

Сравнение методов

Выбор метода зависит от размера ваших данных и ваших приоритетов. Для небольших массивов может быть достаточно простоты метода временного массива. Для больших массивов прирост производительности метода Arrays.sort() перевешивает его несколько большую пространственную сложность. Метод отдельного индекса предлагает экономичное решение с точки зрения памяти, но его квадратичная временная сложность делает его менее привлекательным для больших наборов данных.