sun*_*oon 5 arrays algorithm data-structures
我们有一组N个数字.所有数字都在1-k之间.
问题是如何找到找到最频繁三联体的最佳方法.
我解决这个问题的方法是:
假设输入是{1,2,3,4,1,2,3,4}
首先从数组中的第二个元素开始搜索三元组(1,2,3)的计数,直到数组结束.现在我们将计数为1.现在从{2,3,4)开始并搜索数组.
对于每个三元组,我们扫描数组并找到计数.像这样我们运行数组n-1次.
这样我的算法以n*n时间复杂度的顺序运行.有没有更好的方法
这个问题.？
您可以在最坏情况的空间和时间复杂度下做到这一点O(n * log n)：只需将所有三元组插入到平衡二叉搜索树中，然后找到最大值。
或者，您可以使用哈希表来获取O(n)预期时间（如果您选择一个好的哈希函数，实际上通常比搜索树方法更快）。