Если отсортировать массивы и «сжать» примитивным образом, чтобы избежать многократных проходов по одним и тем же эл-там: [1,1,1,1 0,0, 2, 2, 2, 2, 3] -> [(0,2), (1,4),(2,2), (3,1)]
после этого устанавливаем указатели на начало эталонного массива из первой группы и проверяемого из второй и проверяем кол-во совпадений, учитывая второе число.
// arr1, arr2 = проверяемые отсортированные сжатые массивы,
// arr[нечётный_индекс] = эл-т массива,
// arr[чётный_индекс] = кол-во вхождений этого значения
int i, j;
int matches = 0;
for(i = 0, j = 0; i < arr1.size() && j < arr2.size(); )
{
if(arr1[i] == arr2[j])
{
matches+= min(arr1[i+1], arr2[j+1];
i+=2; j+=2;
}
else if(arr1[i] < arr2[j]) { i+=2; }
else { arr2[j] < arr1[i] ) { j+= 2; }
}
Сложность проверки двух сжатых отсортированных массивов O(m+n), m и n их длины.
Некоторые массивы скорее всего будут вообще совпадать. В этом случае лучше перед сравнением вообще посчитать хэш их элементов и перед запуском сравнения сначала сравнить длины и хэши массивов. Если хэши совпадают, то можно пропустить проверку и добавлять длину несжатого массива.
