СРОЧНО!!! ОСТАЛОСЬ МАЛО ВРЕМЕНИ!!! 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.
Из небольших ускорений можно предложить проверять до b[c], дальше всё равно ничего нет. Но всё равно алгоритм будет делать порядка n^2 операций, что при n = 10^5 достаточно много. Кстати, 2*10^9 еще помещается в longint, int64 не нужен.
Можно пойти другим путём. Отсортируем массив 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.
Выглядит просто :) И так... Допустим переменная 'a' = 15, заходим в цикл. Отнимаем от переменной 2. Если переменная 'a' больше 1, то повторяем цикл. И так до того момента пока от переменной не останется 0 или 1. Если переменная равна 0, это значит что переменная четная. А если 1, то переменная нечетная. И так делаем со всеми переменными :)