JS：编写一个函数，遍历字符串列表并返回列表中出现频率最高的前10个字符串
我正在尝试编写一个函数，它遍历字符串列表并返回列表中前 10 个最常用的字符串。我正在尝试为这个问题提出多种解决方案
这是我的第一个解决方案
const list = [
"this",
"is",
"a",
"test",
"which",
"word",
"wins",
"top",
"i",
"don't",
"know",
"off",
"hand",
"do",
"you",
"this",
"a",
"a",
"this",
"test",
"a",
"a",
"do",
"hand",
"hand",
"a",
"whatever",
"what",
"do",
"do"
];
function fn1(strArr) {
const map = new Map()
for(const str of strArr) {
if(map.has(str)) {
map.set(str, map.get(str) + 1)
} else {
map.set(str, 1)
}
}
const sortedMap =[...map.entries()].sort(([_,a], [__,b]) => a < b ? 1 : -1)
return sortedMap.slice(0 , 10).map(([str]) => str)
}
但我似乎找不到这个问题的任何其他解决方案。任何人都可以提出替代建议吗？
另外，需要注意的一件事是列表可能非常大，可能包含 100 万个字符串。所以我们需要尽量减少运行时的复杂度
回答
我相信以下解决方案在实践中是最快的：
n正如您已经完成的那样，将字符串映射到它们的频率。O(n)- 将映射转换为具有字符串/频率对的数组。
O(n) - 使用 Floyd 的方法根据频率将数组转换为 Max-heap（即，通过对从
?n/2? - 1下到 0 的所有索引调用 max-heapify ）。O(n) - 提取顶部元素
k时间。（在你的情况下，k=10。）O(k log n)
（我在这里不提供任何代码，因为它基本上包括调用二进制堆库（请参阅此处以获得高度优化的实现）。
分析
渐近复杂度O(n + k log n)低于O(n log k)Chaos Monkey 提供的解决方案。对于小k（例如 10），可能不会有任何显着差异。较大的差异变得更加明显k（只要k ? n; 对于更大的k，请参阅下面的“替代方案”）。还要注意，第1步和第2步的常数因子是1，第3步的常数因子平均也很小（1.8814），所以总的常数因子小于4。
选择
有一个解决方案可以O(n)平均解决问题，也有一个小的常数因子，这对于更大的k（即k接近时n/2）效率更高。缺点是（极不可能的）最坏情况的复杂性是O(n²)：
n正如您已经完成的那样，将字符串映射到它们的频率。O(n)- 将映射转换为具有字符串/频率对的数组。
O(n) - 应用Quickselect（与 Quicksort 完全一样，但只是在分区的一侧递归）以找到
k最大频率。左边的所有元素都更大，因此结果是kQuickselected 数组的第一个元素。O(n)平均，O(n²)最坏情况。
可以O(n)使用中位数枢轴选择的中位数来实现具有保证复杂性的 Quickselect 的变体，但这在实践中并不是那么好，因为常数因子非常高。但从学术的角度来看，这将是渐近最优解。
（这是一个用于 Quickselect 的 JavaScript 库，尽管快速浏览，该实现看起来并不适合这种情况：一个好的实现应该执行Dijkstra 风格的 3 路分区。）
基准
一个带有n = 10^6, 的快速而肮脏的基准测试，k = 10仅测量第 2 步之后的运行时间（因为第 1/2 步在所有 5 个方法之间共享）：
Average time for Sort: 7.5 ms
Average time for ChaosMonkey: 10.25 ms
Average time for CountingSort: 5.25 ms
Average time for Mo B. Max-Heap: 4 ms
Average time for Mo B. Alternative (Quickselect): 3.25 ms
https://dotnetfiddle.net/oHRMsp
我的结论是，对于给定的参数，不同方法之间没有太大区别。为简单起见，我只会坚持排序方法，它也适用于n和k。
（很多警告：它是用 C# 编写的（草率的），而不是 JavaScript；它没有经过正确性测试；个别方法没有优化；运行时也可能取决于频率的分布，实现的 Quickselect 是幼稚的，因为它没有优化对于（此处）许多频率相等的常见情况等...）
关于空间的最后说明
所有基准方法都使用额外的O(n)空间，因为它们首先创建频率图（计数排序方法O(n)在频率图顶部使用额外的最坏情况空间进行计数）。可以只用O(1)额外的空间来解决这个问题，但代价是时间复杂度为O(kn²)。