Java数组算法- Big O

Question

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

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

在思考如何做到这一点时，我在考虑使用HashMap或其他强制唯一键值的东西，将字符串存储为键，将频率存储为值。当这一切都完成之后，我就可以遍历map值比较了。

总体而言，这将得到O(n) + O(n) ...我只是想知道有没有更好的方法

编辑：

我知道你不可能比O(n)做得更好，但这里的问题是，一旦我迭代了初始数组来构建HashMap，我就必须对哈希图执行reIterate操作，以找出哪一对的值最高，也就是O(n)。实际上，有没有一种方法可以做到这一点，我只需要迭代整个列表一次

Answer 1

我的2分: O(2n)不坏，但也许你可以做得更好……

您可以使用HashMap<String, Integer>，也可以使用动态更新的WinnerText字符串和WinnerCount整数计数器。然后在最后使用后两者来构建结果字符串，这应该会得到O(n) + O(1)。

Answer 2

可以肯定的是，你必须抛出所有的数组，所以我认为你只需要创建一个结构或类，比如：

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

使用它，然后抛出数组，创建新对象，并在找到现有对象时递增。最后，有较大重复值的就是你要查找的

Answer 3

只要你必须遍历整个列表来拉回你的值，你就永远不会得到比O(n)更好的结果。我能想到的唯一拉回接近O(1)的方法是存储一个" max“实例变量，它在插入过程中计算最大值。

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

一种更好的替代方案(虽然开销很大)是在将值插入数组时存储所有总计数的哈希图。然后，您可以保存一个运行总数，并且存储一个最大值比存储O(n)更接近O(log )。

编辑：

我明白你现在在问什么..。您可以尝试将值存储在二进制搜索树中...这将在您将数据添加到数据结构中时对数据进行排序，对该数据结构的任何回调都将是O(log )表示遍历的get，O(1)表示拉回根(或最大值)。