Cамый частый элемент в 2x отсортированных массивах за O(n)

Question

Найти сколько раз встречается самый частый элемент в объединении двух отсортированных по возрастанию массивах. Элементы могут повторяться. Алгоритм должен работать за линейное время. И дополнительные массивы в целях экономии памяти создавать нельзя.

findMaxCount([1, 2, 9, 10], [2, 2, 10]) => 3

Задача попалась на интервью, решить не смог. Как я понял что-бы добиться линейного времени нужно двигать 2 указателя, но как именно не понятно.

Answer 1

Два указателя и дело в шляпе

int findMaxCount(int[] data1, int[] data2)
{
    int ind1=0; 
    int ind2=0;
        
    int last = 0;
    int lastCount = 0;

    int max = 0;
    int maxCount = 0;   
    
    while(ind1 < data1.Length || ind2 < data2.Length)
    {
        int cur = 0;

        if (ind1 == data1.Length)
            cur = data2[ind2++];        
        else if (ind2 == data2.Length)      
            cur = data1[ind1++];
        else if (data1[ind1] < data2[ind2])         
            cur = data1[ind1++];
        else
            cur = data2[ind2++];
            
        if (cur == last) lastCount++;
        else 
        {
            if (lastCount > maxCount)
            {
                maxCount = lastCount;
                max = last;
            }
            last = cur;
            lastCount = 1;
        }
    }

    if (lastCount > maxCount)
    {
        maxCount = lastCount;
        max = last;
    }

    return max;
}

Проверка

System.out.println(findMaxCount(new[] { 1, 2, 8, 10 }, new[] {2, 2, 3, 3, 10}));

Вывод

Answer 2

Есть довольно известный алгоритм merge sort. И в нём есть фаза слияния, когда даны два отсортированных массива, которые надо объединить в один отсортированный.

Вот именно этот алгоритм и надо использовать. Только вместо того, чтобы писать в массив, надо запоминать только последний элемент и считать, сколько раз он встретился. А если текущий не соврадает с предыдущим, то проверяем, не надо ли обновить результат.

БЛОГ НА HUSL

Cамый частый элемент в 2x отсортированных массивах за O(n)

Ответы (2 шт):