Как посчитать уникальные предметы в списке?

Question

Как бы кто-то посчитал количество уникальных предметов в списке?

Например, скажем, у меня есть {1, 3, 3, 4, 1, 3}, и я хочу получить число 3которые представляют количество уникальных элементов в списке (а именно | A | = 3, если A = {1, 3, 4}).Какой алгоритм кто-то использует для этого?

Я пробовал двойной цикл:

for firstItem to lastItem
  currentItem=a
  for currentItem to lastItem
    currentItem=b
    if a==b then numberOfDublicates++
uniqueItems=numberOfItems-numberOfDublicates

Это не работает, так как подсчитывает дубликаты больше раз, чем фактически необходимо.Для примера в начале это будет:

1. Для первого цикла будет насчитываться +1 дубликатов для номера 1. В списке.
2. Для второй цикл он будет насчитывать +2 дубликата для номера 3. в списке.
3. . Для третий цикл он будет считать +1 дубликатов для номера 3 снова (при пересчетепоследний «3») и вот где возникает проблема.

Есть идеи, как решить эту проблему?

Answer 1

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

Answer 2

Вы можете проверить, есть ли дубликаты после номера. Если нет, увеличьте значение uniqueCount:

uniqueCount = 0;
for (i=0;i<size;i++) {
  bool isUnique = true;
  for (j=i+1;j<size;j++)
     if (arr[i] == arr[j] {
       isUnique = false;
       break;
     }
  }
  if(isUnique) {
    uniqueCount ++;
  }
}

Вышеупомянутый подход O(N^2) во времени и O(1) в пространстве.

Другой подход заключается в сортировке входного массива, который будет помещать дубликаты элементов рядом друг с другом, а затем искать соседние элементы массива. Этот подход O(NlgN) во времени и O(1) в пространстве.

Если вам разрешено использовать дополнительное пространство, вы можете сделать это за O(N) время и O(N) пространство, используя хеш. Ключами для хэша являются элементы массива, а значения - их частоты.

В конце хеширования вы можете получить счет только тех хеш-ключей, которые имеют значение 1.

Answer 3

Сортируйте его, используя приличный алгоритм сортировки, такой как mergesort или heapsort (как habe O (n log n) как наихудший случай), и переберите отсортированный список:

sorted_list = sort(list)
unique_count = 0
last = sorted_list[0]

for item in sorted_list[1:]:
  if not item == last:
    unique_count += 1
  last = item

Answer 4

list.sort();
for (i = 0; i < list.size() - 1; i++)
  if (list.get(i)==list.get(i+1)
    duplicates++;

Answer 5

Держите словарь и добавляйте счетчик в цикле

Вот как это будет выглядеть на c #

int[] items = {1, 3, 3, 4, 1, 3};
Dictionary<int,int> dic = new Dictionary<int,int>();
foreach(int item in items)
   dic[item]++

Конечно, в C # есть способ LINQ, но, как я понимаю, вопрос является общим;)