arrays - 如何使用 'Divide and Conquer' 方法计算出现次数

Question

我正在寻找一种算法来计算数组中每个元素出现的次数，使用分而治之的方法。

这是一个例子；

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

谁能至少告诉我从哪里开始？谢谢

Answer 1

您可以 merge sort数组，然后在排序数组的单次传递中输出值及其计数。

或者，您也可以将输入数组映射到对数组:(number, 1)。然后像merge sort中那样分而治之，但在合并阶段，您递增相同数字的计数，而不是多次输出。

Python 示例代码

#!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)]