多数投票算法的技术在哪些领域可以应用？

Question

正如在线性时间多数算法？的答案中所看到的，可以在线性时间和log(n)空间中计算元素数组的大多数。

已经证明，每个看到这个算法的人都认为它是一种很酷的技术。但是这个想法是否推广到新算法呢？

似乎这个算法的隐藏力量在于保持一个起复杂作用的计数器 -- 例如“(目前大多数元素的计数) - (目前第二多数元素的计数)”。是否有基于相同思想的其他算法？

- dsg

Answer 1

嗯，首先让我们了解一下算法为什么有效，以便于“隔离”这些思想。

该算法的关键是如果你有一个多数元素，那么你可以将其每个出现与“另一个”元素匹配，然后你就有了一些更多的“备用”。

所以，我们只需要一个计数器来计算我们客人答案的“备用”出现次数。如果它达到0，则它不是从我们“选举”“当前”元素作为主要客人元素到“当前”位置开始的子序列的大多数元素。此外，由于我们的“客人”元素匹配所考虑子序列中的每个其他元素出现，因此在所考虑的子序列中没有主要元素。

现在，由于：

1. 我们的算法仅在存在主要元素时才给出正确答案，而
2. 如果存在主要元素，则当计数器归零时忽略“当前”子序列时它仍将存在

很明显，通过反证法可以看出，如果存在主要元素，则我们有整个序列的后缀，在其中计数器永远不会归零。

现在：可以在新的O（1）大小O（n）时间算法中利用的想法是什么？

对我来说，每当你必须计算元素序列上的属性P时，就可以应用此技术，该序列：

1. 如果Q（seq [n，m + 1]）不成立，则可以将其从seq [n，m]扩展到seq [n，m + 1]，时间为O（1）
2. 如果Q（seq [n，j]）成立，则可以从P（seq [n，j]）和P（seq [j，m]）计算出P（seq [n，m]），并且可以在O（1）时间和空间内计算P（seq [n，m]）。

在我们的情况下，P是我们“选举”的主要元素的“备用”出现次数，而Q是“P为零”。

如果您以这种方式看待事物，那么最长公共子序列也利用了相同的思想（关于其“酷炫因素”的问题我不确定）。

- akappa

---

你关于 P 和 Q 的一般描述听起来像是动态规划的描述。你是不是想说的比“Boyer-Moore 是一种动态规划算法”更多？ - dsg

@dsg：也许你可以将其视为一种动态规划形式，但主要点是在点1）和2）中的O（1）时间和空间以及由属性Q驱动的2）上的“分解”属性，这使您在某种意义上“忘记”了到目前为止所见过的东西。 - akappa

Answer 2

Jaydev Misra和David Gries有一篇论文，名为Finding Repeated Elements（ACM页面），将其推广到元素重复超过n/k次（k=2是主要问题）。

当然，这可能与原始问题非常相似，您可能正在寻找“不同”的算法。

以下是一个可能不同的示例。

提供一种算法，检测括号字符串（'（'和'）'）是否格式正确。

我相信标准解决方案是维护计数器。

附注：

至于声称不能为常量空间等的答案，请向他们询问计算模型。例如，在WORD RAM模型中，您假设整数/数组索引等为O（1）。

很多人错误地混合和匹配模型。例如，他们会愉快地把n个整数的输入数组设为O（n），将数组索引设为O（1）空间，但是他们认为计数器是Omega（log n）等等，这是无稽之谈。如果他们想考虑位数大小，则输入本身就是Omega（n log n）等等。

- Aryabhatta

---

这是关于职业杯的同样问题链接：http://www.careercup.com/question?id=14099679 - dsg

Answer 3

对于想要了解该算法的作用和原理的人们，请查看我的详细答案。

在标准多数投票算法中，您需要找到在流中至少出现n/2次的元素，其中n是流的大小。您可以在O(n)时间(带有微小的常数和O(log(n))空间，最坏情况下并且高度不太可能)内完成此操作。

---

广义算法允许您找到k个最频繁的项目，每个项目在原始流中至少出现n/(k+1)次。请注意，如果k=1，则最终得到原始问题。

解决这个问题的方法与原始问题非常相似，只是您需要维护k个计数器和k个可能的元素，而不是一个计数器和一个可能的元素。现在逻辑以类似的方式进行。您遍历数组，如果元素在可能的元素中，则增加其计数器，如果一个计数器为零-请使用新元素替换该计数器的元素。否则，只需减少值即可。

与原始多数投票算法一样，您需要保证您具有这些k个主要元素，否则您必须对数组进行另一次遍历，以验证您先前找到的可能元素是否正确。这是我的Python尝试(尚未进行彻底测试)。

from collections import defaultdict
def majority_element_general(arr, k=1):
    counter, i = defaultdict(int), 0
    while len(counter) < k and i < len(arr):
        counter[arr[i]] += 1
        i += 1

    for i in arr[i:]:
        if i in counter:
            counter[i] += 1
        elif len(counter) < k:
            counter[i] = 1
        else:
            fields_to_remove = []
            for el in counter:
                if counter[el] > 1:
                    counter[el] -= 1
                else:
                    fields_to_remove.append(el)
            for el in fields_to_remove:
                del counter[el]

    potential_elements = counter.keys()
    # might want to check that they are really frequent.
    return potential_elements

- Salvador Dali