在 O(n) 时间和 O(1) 额外空间内找到最大重复数（出现次数最多的数） .
我认为我可以使用维护计数数组的计数排序阶段，然后可以在 O(N) 中完成。我对吗 ？
但如何处理多余的空间。还有其他高效的算法吗？
如果没有进一步了解数组中可能的数字，我认为这是不可能的。为了直观起见，请考虑以下事项：对于您准备使用的任何恒定内存量（c = O(1)) 存在一个序列使得在点n-1有c+1正确答案的可能性，只有最后一个数字才能打破平局。在这种情况下，具有恒定内存的算法c无法一次性找到答案。这对于多次（恒定数量）的通过类似地起作用。
让我们看看我们能做什么。
- 如果我们知道最多有
k唯一的数字，我们可以找到答案O(n) with O(k)通过保留计数数组（或具有恒定查找成本的无序映射，如果k数字不必是连续的）。但如果我们无法约束k以外k<n这变成O(n)在最坏的情况下有额外的空间。
- 如果我们对数组进行排序
O(n log(n))，然后我们可以找到答案O(n)。所以总复杂度是O(n log(n)) with O(1)额外的空间。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
