@anton_mra

Как преобразовать алгоритм нахождения различных элементов в массиве?

Дан массив с элементами типа 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);

end.

Помогите, пожалуйста.
  • Вопрос задан
  • 28 просмотров
Пригласить эксперта
Ответы на вопрос 1
longclaps
@longclaps
Дан массив с элементами типа byte.
a[i]:=random(20)-10;
Что это за дерьмо? byte: 0..255

Я уже не знаю, что делать, не представляю себе такой алгоритм...
Во всякой непонятной ситуации иди спать.

var counter: array[byte] of integer;
for i := 1 to n do begin
    Inc(counter[a[i]]);
end;

и всё.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы