Как преобразовать алгоритм нахождения различных элементов в массиве?
Дан массив с элементами типа byte. Надо узнать количество
различных элементов в нем. Количество действий должно быть
порядка cn, где n - длина массива.
Я сделал задачу в pascalABC, она прекрасно работает. но есть одно НО. Сложность алгоритма должна быть cn, а не n^2 (как у меня).
Это значит нужно убрать вложенность цикла for.
Я уже не знаю, что делать, не представляю себе такой алгоритм...
Листинг ниже:
program zadacha;
const
nmax=100;
type
tArr=array[1..nmax] of byte;
var
a,b: tArr;
i,j,n,m,k: byte;
procedure fillArray(var a:tArr);
var i:integer;
begin
randomize;
for i:=1 to n do
begin
a[i]:=random(20)-10;
end;
end;
procedure printArray(a:tArr;n:byte);
var i:integer;
begin
for i:=1 to n do
begin
write(a[i],' ');
end;
end;
procedure findUnique(var a,b:tArr);
var i,j:integer;
begin
for i:=1 to n do
begin
k:=0;
for j:=1 to n do
begin
if a[i]=a[j] then
inc(k);
end;
if k=1 then
begin
inc(m);
b[m]:=a[i];
end;
end;
end;
begin
m:=0; k:=0;
write('Введите размер массива: '); readln(n);
fillArray(a);
writeln('Массив:');
printArray(a,n);
writeln;
findUnique(a,b);
writeln('Массив из неодинаковых чисел:');
printArray(b,m);
Простой
