求在O(n)个时间和O(1)个额外空间内出现次数最多的数
我认为我可以使用计数排序阶段维护计数数组，然后它可以在O(N)中完成。
但是如何处理额外的空间。有没有其他有效的算法?
如果不进一步了解数组中可能的数字，我认为这是不可能的。对于直觉，请考虑以下内容:对于您准备使用的任何常量内存(c = O(1))，存在一个序列，以便在n-1点有c+1种正确答案的可能性，并且只有最后一个数字才会打破平局。在这种情况下，具有恒定内存c的算法不能一次找到答案。这对于几个(固定数量的)传递也是类似的。
让我们看看我们能做些什么。
- 如果我们知道最多有
k个唯一的数字，我们可以在O(n)中找到答案，O(k)有额外的空间，通过保持一个计数数组(或无序映射，如果k的数字不需要是连续的)。但是，如果我们不能绑定k而不是k<n，那么在最坏的情况下，这将成为O(n)的额外空间。 - 如果我们在
O(n log(n))中对数组进行排序，我们可以在O(n)中找到答案。所以总复杂度是O(n log(n))加上O(1)额外空间。