Удаление дубликатов из списка целых чисел в Delphi

Delphi , Компоненты и Классы , Списки

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

Базовый подход с использованием списка

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

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>;
var
  List: IList<Integer>;
begin
  List := TCollections.CreateList<Integer>;
  Input.ForEach(
    procedure(const I: Integer)
    begin
      if not List.Contains(I) then
        List.Add(I);
    end);
  Result := List;
end;

Использование словаря для ускорения поиска

Для улучшения производительности можно использовать словарь (или ассоциативный массив), который позволяет быстро проверять наличие элементов. Это ускоряет процесс удаления дубликатов за счет более быстрого доступа к элементам.

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>;
var
  Dictionary: IDictionary<Integer, Integer>;
  Item: Integer;
begin
  Dictionary := TCollections.CreateDictionary<Integer, Integer>;
  for Item in Input do
    Dictionary.AddOrSetValue(Item, 0);
  Result := Dictionary.Keys;
end;

Сортировка списка и сравнение элементов

Еще один способ - сначала отсортировать список, а затем сравнить каждый элемент с последующим. Это решение имеет сложность O(n log n) для сортировки и O(n) для поиска дубликатов, что в сумме дает O(n log n).

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>;
var
  List: IList<Integer>;
  i: Integer;
begin
  List := TCollections.CreateList<Integer>;
  List.Assign(Input); // Копирование входного списка в выходной.
  List.Sort;
  for i := List.Count-1 downto 1 do begin
    if List[i] = List[i-1] then List.Delete(i); 
  end; {for i}
end;

Использование встроенных функций для удаления дубликатов

Наиболее простой и элегантный способ - использовать встроенные функции, такие как TDistinctIterator, которые уже реализованы в библиотеках, таких как Spring.Collections.

uses
  Spring.Collections,
  Spring.Collections.Extensions;
function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>;
begin
  Result := TDistinctIterator<Integer>.Create(Input, nil);
end;

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

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

Создано по материалам из источника по ссылке.

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

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Списки ::