Это для задания и находится в psuedo-коде.Подсчет дубликатов (не обязательно удаление) в массиве в O (n)
Мне нужно найти, сколько целых чисел в массиве уникально, ничего другого, но оно должно быть в O (n), желательно без хеширования.
Спасибо!
А как насчет этого псевдокода?
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;
И premis в том, что необъявленная уникальная [я] является 0
Просто перебирайте каждый элемент в массиве и отслеживайте элементы, которые видите, когда вы видите дубликат, сообщите об этом.
Кроме того, в зависимости от того, как вы отслеживаете элементы, это может быть или не быть O (n), но я оставлю эту часть вам, вы должны что-то узнать по крайней мере.
OMG. и какова сложность «отслеживания»? – Andrey
Я думаю, вы имеете в виду какое-то хеширование? Это то, о чем я думал, по крайней мере, но я не думаю, что это разрешено. – Mosho
Я был на самом деле, думая что-то более похожее на то, что Moravec отправил, используя другой массив, чтобы «отслеживать». И @ Andrey, вы можете отслеживать элементы таким образом без лишней сложности. – adhanlon
Так, так как это для задания, какие идеи у вас до сих пор? Конечно, вы не ожидаете, что мы просто дадим вам ответ на использование как ваш, да? –
Я полагаю, что не должен. Большой проблемой было найти k-й наибольший элемент в массиве, значения не ограничены. Я использовал разделение вместе с функцией для поиска медианы. для удаления/подсчета дубликатов я думал об использовании линейной сортировки, так как я знаю, что значения слева от раздела меньше медианы, но мне нужен O (n) худший случай, тогда я думал о хэшировании, но мы не имеем " Это еще не достигнуто. – Mosho
@Mosho "линейная сортировка" - ошибка. существует линейный поиск. – Andrey