Подсчет дубликатов (не обязательно удаление) в массиве в O (n)

Question

Это для назначения и в псевдокоде.

Мне нужно найти, сколько целых чисел в массиве уникально, и ничего больше, но оно должно быть в O (n), желательно без хеширования.

Спасибо!

Answer 1

А как насчет этого псевдокода?

array randomNumbers;
array unique;
int uniqueCount = 0;

for (i in randomNumbers) {

  unique[i] += 1;
  uniqueCount++; //count all here
  // and remove duplicities here
  if (unique[i] > 1) {
    uniqueCount--;
  }
}
return uniqueCount;

И предпосылка в том, что необъявленный уникальный [i] равен 0

Answer 2

Просто итерируйте по каждому элементу в массиве и отслеживайте элементы, которые вы видите, когда увидите дубликат, сообщите об этом.

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