在不同数组中查找"最常见元素"的算法

Question

我有5个数组,其中包含一些插入的元素(数字):

1,4,8,10
1,2,3,4,11,15
2,4,20,21
2,30

我需要在这些数组中找到最常见的元素,并且每个元素都应该一直持续到最后(参见下面的示例).在这个例子中,它是粗体组合(或者是相同的一个,但最后是"30",它是"相同的")因为它包含最少数量的不同元素(只有两个,4和2/30).

这种组合(见下文)并不好,因为如果我有前任."4"它必须"去"直到它结束(下一个数组必须完全不包含"4").所以组合必须一直持续到最后.

1,4,8,10
1,2,3,4,11,15
2,4,20,21
2,30

EDIT2:OR

1,4,8,10
1,2,3,4,11,15
2,4,20,21
2,30

或其他任何东西都不好.

是否有一些算法可以加速这个问题(如果我有数千个阵列,每个阵列有数百个元素)？

要说清楚 - 解决方案必须包含最少数量的不同元素,并且必须将组(相同数字)组从第一个 - 较大的组分组到最后一个 - 最小的元素.因此在上面的例子中,4,4,4,2比4,2,2,2更好,因为在第一个例子中,4的组大于2的组.

编辑:更具体.解决方案必须包含最少数量的不同元素,并且这些元素必须从头到尾分组.所以,如果我有三个arrray像

1,2,3
1,4,5
4,5,6

解决方案是1,1,4或1,1,5或1,1,6不是2,5,5,因为1有更大的组(其中两个)而不是2(只有一个).

谢谢.

编辑3:我不能更具体:(

EDIT4:@spintheblack 1,1,1,2,4是正确的解决方案,因为第一次使用的数字(假设在位置1)以后不能使用(除了它在1的SAME组中).我会说分组有"优先级"吗？另外,我没有提到它(对不起),但是数组中的数字没有以任何方式排序,我在这篇文章中输入它是因为我更容易遵循.

Answer 1

我假设“不同的元素”实际上不必是不同的，它们可以在最终的解决方案中重复。也就是说，如果提出[1], [2], [1]明显的答案[1, 2, 1]是允许的。但我们将其视为具有 3 个不同的元素。

如果是这样，那么这是一个Python解决方案：

def find_best_run (first_array, *argv):
    # initialize data structures.
    this_array_best_run = {}
    for x in first_array:
        this_array_best_run[x] = (1, (1,), (x,))

    for this_array in argv:
        # find the best runs ending at each value in this_array
        last_array_best_run = this_array_best_run
        this_array_best_run = {}

        for x in this_array:
            for (y, pattern) in last_array_best_run.iteritems():
                (distinct_count, lengths, elements) = pattern
                if x == y:
                    lengths = tuple(lengths[:-1] + (lengths[-1] + 1,))
                else :
                    distinct_count += 1
                    lengths = tuple(lengths + (1,))
                    elements = tuple(elements + (x,))

                if x not in this_array_best_run:
                    this_array_best_run[x] = (distinct_count, lengths, elements)
                else:
                    (prev_count, prev_lengths, prev_elements) = this_array_best_run[x]
                    if distinct_count < prev_count or prev_lengths < lengths:
                        this_array_best_run[x] = (distinct_count, lengths, elements)

    # find the best overall run
    best_count = len(argv) + 10 # Needs to be bigger than any possible answer.
    for (distinct_count, lengths, elements) in this_array_best_run.itervalues():
        if distinct_count < best_count:
            best_count = distinct_count
            best_lengths = lengths
            best_elements = elements
        elif distinct_count == best_count and best_lengths < lengths:
            best_count = distinct_count
            best_lengths = lengths
            best_elements = elements

    # convert it into a more normal representation.                
    answer = []
    for (length, element) in zip(best_lengths, elements):
        answer.extend([element] * length)

    return answer

# example
print find_best_run(
    [1,4,8,10],
    [1,2,3,4,11,15],
    [2,4,20,21],
    [2,30]) # prints [4, 4, 4, 30]

这是一个解释。字典...this_run的键是当前数组中的元素，它们的值是 tuples (distinct_count, lengths, elements)。我们试图最小化distinct_count，然后最大化长度（长度是一个元组，因此这将更喜欢第一个位置具有最大值的元素）并跟踪末尾的元素。在每个步骤中，我都会构建所有可能的运行，这些运行是到前一个数组的运行与按顺序排列的下一个元素的组合，并找到哪些对于当前来说是最好的。当我到达最后时，我会选择最好的整体运行，然后将其转换为传统的表示形式并将其返回。

如果您有Nlength 的数组M，则这应该需要O(N*M*M)一些时间来运行。