java - 确定在 O(n) 时间和 O(1) 空间内出现次数最多的元素

Question

首先让我声明这不是作业问题。我正在尝试设计一个缓存，其逐出策略取决于缓存中出现次数最多的条目。在软件方面，假设我们有一个包含不同元素的数组，我们只想找到出现次数最多的元素。例如:{1,2,2,5,7,3,2,3} 应该返回 2。由于我使用的是硬件，简单的 O(n^2) 解决方案将需要巨大的硬件开销。使用哈希表的更聪明的解决方案适用于软件，因为哈希表的大小可以改变，但在硬件中，我将有一个固定大小的哈希表，可能不会那么大，所以冲突会导致错误的决定。我的问题是，在软件中，我们能否在O(n) 时间复杂度和O(1) 空间内解决上述问题？

Answer 1

不可能有O(n) 时间，O(1) 空间的解决方案，至少对于一般情况是这样。

作为amit points out ，通过解决这个问题，我们找到了 element distinctness problem 的解决方案(确定列表中的所有元素是否不同)已被证明在不使用元素索引计算机内存时花费 Θ(n log n) 时间。如果我们要使用元素来索引计算机的内存，给定一个无限范围的值，这至少需要 Θ(n) 空间。考虑到将这个问题简化为那个问题，那个问题的界限对这个问题强制执行相同的界限。

但是，实际上，如果除了通常用于存储每个元素的类型具有固定大小(例如 32 位整数)之外没有其他原因，范围将主要是有界的。如果是这种情况，这将允许 O(n) 时间，O(1) 空间解决方案，尽管由于涉及大常数因子(因为时间和空间复杂度将取决于值的范围)。

2个选项:

• Counting sort

  Keeping an array of the number of occurrences of each element (the array index being the element), outputting the most frequent.

  如果您有一个有限范围的值，这种方法将是 O(1) 空间(和 O(n) 时间)。但从技术上讲，哈希表方法也是如此，因此这里的常数因子可能太大而无法接受。

  相关选项是radix sort (有一个就地变体，类似于快速排序)和 bucket sort .

• Quicksort

  Repeatedly partitioning the data based on a selected pivot (through swapping) and recursing on the partitions.

  排序后我们可以遍历数组，跟踪连续元素的最大数量。

  这将花费 O(n log n) 时间和 O(1) 空间。