СРОЧНО!!! ОСТАЛОСЬ МАЛО ВРЕМЕНИ!!! 15 БАЛЛОВ!!! Нужно ускорить работу программы по нахождению количества различных элементов в массиве. Массив дост...

СРОЧНО!!! ОСТАЛОСЬ МАЛО ВРЕМЕНИ!!! 15 БАЛЛОВ!!! Нужно ускорить работу программы по нахождению количества различных элементов в массиве. Массив дост...СРОЧНО!!! ОСТАЛОСЬ МАЛО ВРЕМЕНИ!!! 15 БАЛЛОВ!!! Нужно ускорить работу программы по нахождению количества различных элементов в массиве. Массив достигает до 100 000 элементов, а сами элементы до 2 000 000 000. Код написан снизу. Можно что-то добавить или изменить, можно вообще другой код написать....
Гость
Ответ(ы) на вопрос:
Гость
Из небольших ускорений можно предложить проверять до 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.
Не нашли ответ?
Ответить на вопрос
Похожие вопросы