首先我要说这不是一个家庭作业问题.我正在尝试设计一个缓存,其驱逐策略取决于缓存中发生率最高的条目.在软件方面,假设我们有一个包含不同元素的数组,我们只想找到最常出现的元素.例如:{1,2,2,5,7,3,2,3}应返回2.由于我正在使用硬件,因此天真的O(n ^ 2)解决方案需要巨大的硬件开销.使用哈希表的更智能的解决方案适用于软件,因为哈希表大小可以改变,但在硬件中,我将有一个固定大小的哈希表,可能不是那么大,因此冲突将导致错误的决定.我的问题是,在软件中,我们可以在O(n)时间复杂度和O(1)空间中解决上述问题吗？
Duk*_*ing 14
没有O(n)时间,O(1)空间解决方案,至少不适用于通用案例.
正如amit指出的那样,通过解决这个问题,我们找到了元素清晰度问题的解决方案(确定列表的所有元素是否都是不同的),已经证明?(n log n)在不使用元素索引计算机内存时需要时间.如果我们使用元素来索引计算机的内存,给定一个无限范围的值,这至少需要?(n)空间.鉴于此问题的减少,该问题的界限对此问题强制执行相同的界限.
然而,实际上,如果没有其他原因,通常用于存储每个元素的类型具有固定大小(例如,32位整数),则该范围将主要是有界的.如果是这种情况,这将允许O(n)时间,O(1)空间解决方案,尽管可能太慢并且由于涉及大的常数因素而使用太多空间(因为时间和空间复杂性将取决于值的范围).
2个选项:
保持每个元素出现次数的数组(数组索引是元素),输出最频繁.
如果你有一个有限的值范围,这种方法将是O(1)空间(和O(n)时间).但技术上哈希表方法也是如此,因此这里的常数因素可能太大而无法接受.
基于选定的数据透视表(通过交换)重复分区数据并在分区上递归.
排序后,我们可以遍历数组,跟踪连续元素的最大数量.
这需要O(n log n)时间和O(1)空间.