freepascal.ru

Дан целочисленный массив размера N. Найти максимальное количество его одинаковых элементов.

некоем образом не получается

А какими пробовали?

Способ "в лоб", не эффективный (сложность N*N):
Берём элементы заданного массива и считаем сколько раз они встречались. Помним максимум этого количества.
После окончания этот максимум и есть ответ.

Способ сложности N+NlogN:
1. Сортируем заданный массив.
2. Считаем максимум длин цепочек из одинаковых элементов - это и есть ответ.

Есть и более эффективные способы. Особенно в частных случаях. Например, если в массиве только 0 и 1, достаточно одного прохода.

А я беру, например, Постгес. Создаю БД и таблицу. Заполняю таблицу элементами данного массива, причем, поле в которое этот массив закачиваю - есть primary key. Сколько раз exception получу, столько и одинаковых элементов+1.

Организуем односвязный список с элементами следующей структуры:
type
PRec = ^TRec;
TRec = record
mNumber : integer; // число из массива
mCount : integer; // счетчик вхождений
mNext : PRec; // поле связи
end;

Далее проходим по массиву (1 раз!) и формируем список так, чтобы при повторниях одинаковых чисел наращивался только счетчик mCount. Осталось лишь пробежать по списку и выбрать максимальный mCount.
По сути список здесь выполняет роль множества особого рода. Эффективней, но немного сложнее, - организовать такое множество через бинарное дерево.
---
Аналогичная задача решена в главе 55 книги Песни о Паскале

Вот самый быстрый, но прожорливый по памяти способ (сложнось линейная)
------------------------
const CSize = ...; // размер массива

var
Numbers: array [0...CSize] of integer; // обрабатываемый массив
Counts: array [0...MaxInt] of integer; // массив счетчиков
i, max : integer;

begin
FillChar(Counts, SizeOf(Counts), 0); // очистка счетчиков
for i:=0 to CSize-1 do Inc( Counts[ Numbers[i] ] ); // накопление счетчиков (число в массиве - это индекс счетчика)
// Осталось пробежаться по массиву Counts и выбрать максимальное значение
max:= MinInt; // ноль или минимальное целое
for i:=0 to MaxInt-1 do if max < Counts[i] then max := Counts[i];
end.
------------------------
На ошибки не проверял.

Oleg_D писал(а):Вот самый быстрый, но прожорливый по памяти способ (сложнось линейная)
------------------------
const CSize = ...; // размер массива

var
Numbers: array [0...CSize] of integer; // обрабатываемый массив
Counts: array [0...MaxInt] of integer; // массив счетчиков
i, max : integer;

begin
FillChar(Counts, SizeOf(Counts), 0); // очистка счетчиков
for i:=0 to CSize-1 do Inc( Counts[ Numbers[i] ] ); // накопление счетчиков (число в массиве - это индекс счетчика)
// Осталось пробежаться по массиву Counts и выбрать максимальное значение
max:= MinInt; // ноль или минимальное целое
for i:=0 to MaxInt-1 do if max < Counts[i] then max := Counts[i];
end.
------------------------
На ошибки не проверял.

А куда считаются отрицательные числа?
Как будет работать программа для массива:
1 -30000 30000 -30000
?

informat писал(а):А куда считаются отрицательные числа?
Как будет работать программа для массива:
1 -30000 30000 -30000 ?

-----------
const
CSize = ...
CMinNumber = ...
CMaxNumber = ...
var
Numbers: array [0...CSize] of integer; // обрабатываемый массив
Counts: array [CMinNumber...CMaxNumber] of integer; // массив счетчиков
и т.д. ...
------------
Знаки индексов в массиве могут быть любыми.
Идея, конечно, дурацкая, но в принципе - рабочая, если (CMaxNumber-CMinNumber) не слишком велико.