Вопрос по информатике:
СРОЧНО!!! ОСТАЛОСЬ МАЛО ВРЕМЕНИ!!! 15 БАЛЛОВ!!! Нужно ускорить работу программы по нахождению количества различных элементов в массиве. Массив достигает до 100 000 элементов, а сами элементы до 2 000 000 000. Код написан снизу. Можно что-то добавить или изменить, можно вообще другой код написать. Даю 15 чистых баллов. Язык паскаль (Free Pascal Compiler 3.0.0). Надеюсь на вашу помощь!!!!
var
a, b: array [1..100000] of int64;
i, n, c, j: longint;
tratata, d: boolean;
begin
readln(n);
for i := 1 to n do
begin
read(a[i]);
if a[i] = 0 then tratata := true;
d := false;
for j := 1 to n do
if a[i] = b[j] then d := true;
if not d then begin
inc(c);
b[c] := a[i];
end;
end;
if tratata then writeln(c + 1)
else writeln(c);
end.
- 08.07.2017 08:16
- Информатика
- remove_red_eye 5222
- thumb_up 28
Ответы и объяснения 1
Можно пойти другим путём. Отсортируем массив A[i] за n log n, а потом для того, чтобы определить уникальные элементы, достаточно одного прохода по массиву.
Я буду сортировать сортировкой слиянием, вы можете использовать любую другую достаточно быструю сортировку.
procedure merge(var a: array of longint; left1, right1, left2, right2: integer);
var
temp: array of longint;
i, j, k: integer;
begin
setLength(temp, right1 - left1 + right2 - left2 + 2);
i := left1;
j := left2;
k := 0;
while (i <= right1) and (j <= right2) do
begin
if a[i] <= a[j] then
begin
temp[k] := a[i];
inc(i);
end else begin
temp[k] := a[j];
inc(j);
end;
inc(k);
end;
while i <= right1 do
begin
temp[k] := a[i];
inc(k);
inc(i);
end;
while j <= right2 do
begin
temp[k] := a[j];
inc(k);
inc(j);
end;
for i := left1 to right1 do
a[i] := temp[i - left1];
for j := left2 to right2 do
a[j] := temp[j - left2 + right1 - left1 + 1];
end;
procedure mergeSort(var a: array of longint; left, right: integer);
var
t: longint;
begin
if right - left = 0 then exit;
if right - left = 1 then
begin
if a[left] > a[right] then
begin
t := a[left];
a[left] := a[right];
a[right] := t;
end;
exit;
end;
mergeSort(a, left, (left + right) div 2);
mergeSort(a, (left + right) div 2 + 1, right);
merge(a, left, (left + right) div 2, (left + right) div 2 + 1, right);
end;
var
a: array of longint;
i, n, count: integer;
begin
read(n);
setLength(a, n);
for i := 0 to n - 1 do
read(a[i]);
mergeSort(a, 0, n - 1);
count := 1;
for i := 1 to n - 1 do
if a[i] a[i - 1] then
inc(count);
writeln(count);
end.
- 09.07.2017 10:00
- thumb_up 8
Знаете ответ? Поделитесь им!
Есть сомнения?
Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.
Трудности с домашними заданиями? Не стесняйтесь попросить о помощи - смело задавайте вопросы!
Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.