0

关于大 O 表示法，解决以下问题的最佳方法是什么？

给定一个大小为 N 的字符串数组。遍历该数组并返回一个字符串，该字符串包含在数组中重复次数最多的字符串。此外，返回的字符串应该重复字符串在数组中的次数。前任。如果在数组中“Bob”是找到最多的字符串，并且找到了 3 次，则返回的字符串应该是“BobBobBob”

在考虑如何做到这一点时，我正在考虑使用 HashMap 或其他强制唯一键值的东西，将字符串存储为键，将频率存储为值。当一切都说完之后，我就需要遍历地图比较值..

总的来说，这会给我 O(n) + O(n) ...我只是想知道是否有更好的方法来做到这一点

编辑：

我知道你不能比 O(n) 做得更好，但这里的问题是，一旦我迭代初始数组以构建 HashMap，我将不得不重新迭代 hashmap 以确定哪对具有最高值，这将再次是 O(n) .. 基本上有没有办法做到这一点，我只需要迭代整个列表一次

4

3 回答 3

3

我的 2 美分：O(2n) 还不错，但也许你可以做得更好......

您可以使用 a HashMap<String, Integer>，然后还可以使用即时更新的WinnerText字符串和WinnerCount整数计数器。然后最后你使用后两个来构建你的结果字符串，这应该给你 O(n) + O(1)。

于 2013-10-31T13:39:16.643 回答
1

可以肯定的是，您必须扔掉所有数组，所以我认为您只需要创建一个结构或类，例如：

     class myString{
       public String str ;
       public int repetition ;
       public myString(String str){
             this.str = str ;
             repetition = 1 ;
       }
       public void increment(){
              repetition+=1;
       }
      }

您使用它并抛出您的数组并创建新对象并在找到现有对象时递增。最后，具有大重复值的就是您要搜索的内容

于 2013-10-31T13:41:07.763 回答
1

只要您必须循环遍历整个列表以拉回您的值，您就永远不会比 O(n) 更好。我能想到的唯一方法是将任何接近 O(1) 的东西拉回是存储一个“max”实例变量，该变量在插入期间计算最大值。

但实际上，您只是用 O(1) 插入换取 O(n) 插入。但取决于您将更频繁地使用哪个，这可能对您有用。

一个更好的可能替代方案（尽管开销确实很大）是在将值插入数组时存储所有总计数的哈希图。然后你可以保持一个运行总数并存储一个最大值会比 O(n) 更接近 O(log n) 更好。

编辑：

我明白你现在在问什么...您可以尝试将您的值存储在二叉搜索树中...当您将数据添加到数据结构中时，它将对您的数据进行排序，并且对该数据结构的任何召回都将是 O(log n) 用于遍历的 get 和 O(1) 以拉回根（或最大值）。

于 2013-10-31T13:47:02.200 回答