arrays - 如何使用“分而治之”方法计算发生次数

标签 arrays algorithm find-occurrences

我正在寻找一种算法来计算数组中每个元素的出现次数,使用分治方法。
这里有一个例子;

Input: 12-3-5-3-12-3
OutPut: (12, 2), (3, 3), (5,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)]                                                       

关于arrays - 如何使用“分而治之”方法计算发生次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33499806/

相关文章:

arrays - 用冒号分割字符串

c - 基本C程序,巴比伦算法

python - 如何查找字符串中单词的出现率和出现率;如何解决错误

c - 如何修复段错误 11 错误?

r - 如何使用R从具有多列的数据框中计算(共)发生矩阵?

c++ - 任何将 vector 传递给需要某种大小的数组引用的遗留 API 的方法

c++ - 将多维数组传递给函数(c++)?

javascript - 根据另一个数组过滤数组并合并

python - 如何找到从 1 到达 A 的最小合法跳跃次数?

algorithm - 使用Trie,时间复杂度为O(m)的单词搜索-m是单词的大小