Определить количество уникальных значений в массиве

Question

Я ищу эффективный способ определения количества уникальных значений в массиве.

Мой текущий подход:

1. Массив быстрой сортировки целых чисел
2. Затем запустите цикл для сравнения элементов.

В коде:

  yearHolder := '';
  for I := 0 to  High(yearArray) do
  begin
    currYear := yearArray[i];
    if (yearHolder <> currYear) then
    begin
      yearHolder := currYear;
      Inc(uniqueYearNumber);
    end;
  end;

Answer 1

Вот пример с THashedStringList:

hl := THashedStringList.Create; // in Inifiles
try
  hl.Sorted := True;
  hl.Duplicates := dupIgnore; // ignores attempts to add duplicates
  for i := 0 to  High(yearArray) do
    hl.Add(yearArray[i]);
  uniqueYearCount := hl.Count;
finally
  hl.Free;
end;

Answer 2

В общем, вы можете использовать этот алгоритм:

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

Однако, в вашем случае ваши переменные называются «year». Если это действительно год, это проще, потому что годы имеют очень ограниченный диапазон. Скажем, диапазона 0-3000 должно быть достаточно. Таким образом, вместо хеш-таблицы вы можете использовать простой массив счетчиков. Инициализируйте это с 0s. Затем, когда вы увидите 2009 год, увеличьте элемент arr [2009]. В конце подсчитайте количество элементов с arr [i]> = 1.

Answer 3

В Delphi с использованием DeHL мы говорим: List uniqueWidgets: = List.Create (MassiveListOfNonUniqueWidgets.Distinct ());

: P

Answer 4

Я бы порекомендовал добавить элементы в Set и после завершения прочитать размер полученного Set . Поскольку Set s не допускает дублирования в Java, DDL, .Net и многих других (если не на всех языках), это безопасный, дешевый и надежный метод.

Answer 5

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

До D2009, есть только THashedStringList (для работы которого требуется куча дорогостоящих чисел -> преобразования строк и хэши строк), но если у вас есть D2009, то Generics.Collections * В блоке 1006 * есть несколько интересных структур данных.

Answer 6

Более эффективным алгоритмом было бы выгрузить все хеш-таблицу (не уверен, что Delphi даже имеет это).

1. Итерация по списку (в этом случае yearArray) и использование значений в качестве ключей в хэш-таблице.
2. Получить количество ключей в хеш-таблице.