C++

[FRikaZOid]

Товарищи, такая задача: подсчитать количество различных цифр в массиве. n - размер массива, k - количество различных чисел. Задача то не сложная, но как это сделать за n+k шагов?

Comments

[lucky-))]

FRikaZOid что-то условие какое-то путанное или временная оценка не та.

[FRikaZOid]

Idealist-)) Нет, все верно. Условие задачи в сборнике Шена. Оно же вот тут: http://www.bspu.secna.ru/Department...shen/node3.html. Задача 1.2.9. Да плюс еще одно условие: без использования дополнительных массивов.





Я тут набросал немного.. Не знаю, правильный ли ход мыслей? Что скажите?





int func(char A[], int n) // 1

{

int T=0;

for(int i=0;i<n;i++) //O(n)

{

switch(A[i])

{

case 1: T|=1; break;

case 2: T|=2; break;

case 3: T|=4; break;

case 4: T|=8; break;

case 5: T|=16; break;

case 6: T|=32; break;

case 7: T|=64; break;

case 8: T|=128; break;

case 9: T|=256; break;

case 0: T|=512; break;

}

}

i=0;

for(;T!=0;T>>=1)

{

if((1&T)==1)

i++;

}

return i;



}

[FRikaZOid]

задача решилась намного проще, чем я думал. И мыслил я не правильно.. Всем спасибо)

[Геральд]

Гы... Сделай за n шагов)))

[FRikaZOid]

Геральд Помоему, это уже точно не реально..

[Геральд]

На 1Сv8 сделаю. В одном цикле от0 до n-1.

[FRikaZOid]

Геральд Ну давай, потом покажешь)