首先让我声明这不是作业问题。我正在尝试设计一个缓存，其逐出策略取决于缓存中出现次数最多的条目。在软件方面，假设我们有一个包含不同元素的数组，我们只想找到出现次数最多的元素。例如:{1,2,2,5,7,3,2,3} 应该返回 2。由于我使用的是硬件，简单的 O(n^2) 解决方案将需要巨大的硬件开销。使用哈希表的更聪明的解决方案适用于软件，因为哈希表的大小可以改变，但在硬件中，我将有一个固定大小的哈希表，可能不会那么大，所以冲突会导致错误的决定。我的问题是，在软件中，我们能否在O(n) 时间复杂度和O(1) 空间内解决上述问题？
最佳答案
不可能有O(n) 时间，O(1) 空间的解决方案，至少对于一般情况是这样。
作为amit points out ，通过解决这个问题，我们找到了 element distinctness problem 的解决方案(确定列表中的所有元素是否不同)已被证明在不使用元素索引计算机内存时花费 Θ(n log n) 时间。如果我们要使用元素来索引计算机的内存，给定一个无限范围的值，这至少需要 Θ(n) 空间。考虑到将这个问题简化为那个问题，那个问题的界限对这个问题强制执行相同的界限。
但是，实际上，如果除了通常用于存储每个元素的类型具有固定大小(例如 32 位整数)之外没有其他原因，范围将主要是有界的。如果是这种情况，这将允许 O(n) 时间，O(1) 空间解决方案，尽管由于涉及大常数因子(因为时间和空间复杂度将取决于值的范围)。
2个选项:
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 .
Repeatedly partitioning the data based on a selected pivot (through swapping) and recursing on the partitions.
排序后我们可以遍历数组，跟踪连续元素的最大数量。
这将花费 O(n log n) 时间和 O(1) 空间。
关于java - 确定在 O(n) 时间和 O(1) 空间内出现次数最多的元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23261128/
我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123
我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/
我正在编写一个方法，它将在一个类中定义一个实例方法；类似于attr_accessor:classFoocustom_method(:foo)end我通过将custom_method函数添加到Module模块并使用define_method定义方法来实现它，效果很好。但我无法弄清楚如何考虑类(class)的可见性属性。例如，在下面的类中classFoocustom_method(:foo)privatecustom_method(:bar)end第一个生成的方法(foo)必须是公共(public)的，第二个(bar)必须是私有(private)的。我怎么做？或者，如何找到调用我的cust
我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查
这个问题在这里已经有了答案:Railsformattingdate(4个答案)关闭4年前。我想格式化Time.Now函数以显示YYYY-MM-DDHH:MM:SS而不是:“2018-03-0909:47:19+0000”该函数需要放在时间中.现在功能。require‘roo’require‘roo-xls’require‘byebug’file_name=ARGV.first||“Template.xlsx”excel_file=Roo::Spreadsheet.open(“./#{file_name}“,extension::xlsx)xml=Nokogiri::XML::Build
几个月前，我读了一篇关于rubygem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：
我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s
我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www
查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用
我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我
