在数组中找到最频繁的三元组

Question

我们有一个包含N个数字的数组，所有数字都在1-k之间。

问题是如何找到最频繁的三元组的最佳方法。

我对这个问题的解决方法是：

假设输入是{1,2,3,4,1,2,3,4}

首先从数组的第二个元素开始搜索三元组(1,2,3)的计数，一直到数组的末尾。现在我们的计数为1。现在以{2,3,4}开始并搜索数组。

对于每个三元组，我们扫描数组并查找计数。像这样，我们运行n-1次数组。

我的算法以n*n的时间复杂度运行。有没有更好的方法来解决这个问题呢？

- sunmoon

---

你对“三元组”的定义是什么——任意三个连续的数字，还是只有任意三个连续的整数？“3,4,1”是一个三元组吗？ - High Performance Mark

你期望的空间复杂度是多少？ - jackalope

你是否知道你需要的“三元组”，还是打算让算法来找到它？ - bonCodigo

@bonCodigo：“查找最常见的三元组” - Niklas B.

+1 给这个问题 :) @Niklas 当你说“确定性”时，我得到的印象是你将定义所有可能的“三元组”，然后搜索它的最大出现次数..另外如何定义“三元组”也是另一个问题.. ;) - bonCodigo

@sunmoon 你认为三元组是2、3、4！我认为它们是1、2、3！我的意思是你应该先确定三元组的规则！ - SaidbakR

Answer 1

你可以在最坏情况下的时间和空间复杂度为 O(n * log n) 的情况下完成它：只需将所有三元组插入到平衡二叉搜索树中，然后找到最大值即可。

或者，你可以使用哈希表来获得期望时间复杂度为 O(n)（如果选择一个好的哈希函数，则通常比搜索树方法更快）。

- Niklas B.

Answer 2

是否存在内存限制？如果有，那么这个解决方案可能很好：对数组进行迭代，并为每个三元组构建一个表示对象（或在C#中实现的结构体），该表示对象将作为键进入映射表，而三元组计数器则作为其值。

如果适当地实现hash和equals函数，则可以找到“最受欢迎”的三元组，无论数字顺序如何，例如1,2,3 != 2,1,3或1,2,3 == 2,1,3

在迭代整个数组之后，您需要找到最大值，其键将是您的“最受欢迎的”三元组。使用此方法，您还可以找到X个最受欢迎的三元组。此外，您只需扫描数组一次并聚合所有三元组即可，而不需要为每个三元组进行额外的扫描。

- Tom