Как считать события с помощью метода "Разделяй и властвуй"

Question

Я ищу алгоритм для подсчета количества вхождений каждого элемента в массиве, используя метод Divide and Conquer.

Вот пример;

Input: 12-3-5-3-12-3
OutPut: (12, 2), (3, 3), (5,1)

Может кто-нибудь хотя бы дать мне представление, с чего начать? Спасибо

Answer 1

Вы можете объединить отсортировать массив и затем вывести значения с их количеством в один проход отсортированного массива.

В качестве альтернативы, вы также можете сопоставить ваш входной массив с массивом пар: (number, 1), Затем разделите и захватите, как при сортировке слиянием, но на этапе слияния вы увеличиваете количество одинаковых чисел, а не выводите его несколько раз.

Пример кода на питоне

#!python

input = [12, 3, 5, 3, 12, 3];

def count_occurrences(input):
    """ Divide """
    if(len(input) == 0):
        return []
    if(len(input) == 1):
        return [(input[0], 1)]
    left   = count_occurrences(input[:len(input)/2])
    right  = count_occurrences(input[len(input)/2:])

    """ Conquer """
    result = []
    i=0
    j=0
    imax=len(left)
    jmax=len(right)
    while(i<imax and j<jmax):
        if(left[i][0] < right[j][0]):
            result.append(left[i])
            i = i+1
        elif(left[i][0] > right[j][0]):
            result.append(right[j])
            j = j+1
        else:
            result.append((left[i][0], left[i][1]+right[j][1]))
            i = i+1
            j = j+1
    while(i<imax):
        result.append(left[i])
        i = i+1;
    while(j<jmax):
        result.append(right[j])
        j = j+1;

    return result


print (count_occurrences(input))

Это напечатает:

$ python how-to-count-occurrences-with-divide-and-conquer-method.py
[(3, 3), (5, 1), (12, 2)]