Java数组算法-大O

Question

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

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

在考虑如何执行此操作时，我正在考虑使用 HashMap 或其他可以强制使用唯一键值的东西，将字符串存储为键，将频率存储为值。当一切都说完之后，我将不得不遍历 map 比较值..

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

编辑:

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

Answer 1

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

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