时间复杂度 |根据分数查找玩家的排名
Time Complexity | Find ranks of players given their scores
我在一些论坛上寻找要解决的新问题，发现了这个：
给定一个分数数组和一个整数 k。得分相同的玩家排名相同，玩家的排名为“得分高的玩家人数”+1。例如，给定scores = [10, 20, 20, 40]，对应的排名为[4, 2, 2, 1]。只有排名 <= k 的玩家才有资格进入下一轮。 Return 有资格进入下一轮的玩家数量。
我想出了一些方法来解决它，看来我能得到的最佳时间复杂度是 O(nlog(n))，算法如下：
- 对数组进行排序，时间复杂度O(nlogn)
- 然后，从 rank = 1 开始，每次我们传递到较低分数时更新它，所以当 rank <= k 时，不断增加符合条件的玩家数量，时间复杂度为 O(n ), 因为我们最终可能会遍历整个数组。
- return最终计数
另一个想法是创建一些哈希表，将得分作为键值，并将玩家数量作为值：
- 遍历数组，如果我们找到某个得分的人，则将另一个玩家添加到哈希表中该条目的值中，如果我们遇到的得分大于我们的最小得分哈希表，删除最小的分数条目，并放入新的分数（所以，到最后我们只有前 k 个分数）
- 然后将生成的哈希表中的所有值加在一起（或者，至少将相关条目加在一起，因为前 k 个分数并不一定意味着这些是排名前 k 的玩家，但我们知道只有前最多需要 k 个分数才能找到符合条件的数量）
这似乎有时间复杂度O(nk)，因为我们需要遍历整个数组，但每次检查当前k个分数的最小值，以确保我们只保留顶部k 分数。这通常需要比 O(nlogn) 更长的时间。
但是，我觉得一定有比我想出的方法更好的方法。有人有什么建议吗？
这里是原论坛post：https://leetcode.com/discuss/interview-question/1362837/goldman-sachs-new-analyst-2022-oa
另一种思路如下：
- 创建一个频率 table 来计算每个得分的玩家数量。这类似于您在 post 中提到的 hashtable 想法。键是唯一分数，值是该特定分数的玩家数量。
- 使用最小堆将频率为 table 的键推送到堆。一旦堆的长度变得等于
k，对于每次新的推入堆，从堆中弹出一个。这保证您最终在堆中获得 k 最大分数。
- 现在，遍历堆中的元素（不弹出），这些元素是 freq table 的键，然后将 table 中具有这些键的玩家数量相加。
时间复杂度方面，我们在 O(n) 中的初始数组上有 运行 来创建频率 table，我们已经从堆中推送和弹出不同分数的数量，并且因为在最坏的情况下不同分数的数量是 n，所以这使得它成为 O(n * log k) 操作。请注意，由于堆永远不会超过 k，因此它是 log k 而不是 log n。最后，我们遍历了堆中的 k 个元素，并从 freq table 中对它们的值求和，这是 k 操作。
所以，这变成了 n + (n * log k) + k，在大 O 术语中减少到 O(n * log k)。
这是选择问题的一个小变体：您正在寻找列表中第 k 个最小的元素，您需要输出的答案是小于或等于第 k 个元素值的值的数量。有很多可能的解决方案，但标准的是 Quickselect，它可以在线性 O(n) 时间内给出答案。让我们看看针对标准选择问题的各种越来越有效的方法，并查看它们的运行时间：
- 对数字进行排序，并计算最小的 k 个：运行时：
O(n log n).
- 保留一个 min-heap，大小以 k 为界。遍历数组，将每个值推入堆中，并在大小达到 k+1 时弹出。运行时间：
O(n log k)
- Min-Heapify整个数组，弹出k次。有时称为 'heapselect'。运行时间：
O(n + k log n)
- 快速选择。通过随机枢轴选择，它具有
O(n) 预期 run-time 和 O(n^2) worst-case 运行时间，具有良好的平均性能。使用 median-of-medians 枢轴选择，它具有 O(n) worst-case 运行时间，具有更高的常数因子。
如果你查看 C++ 标准库，在算法 header 中，此选择函数称为 第 n 个元素。 In practice, variants of quickselect are often used，例如 introselect 或 randomized-quickselect with heapselect fallback，它试图保留随机 QuickSelect 良好的平均性能但没有 O(n^2) worst-case.
我在一些论坛上寻找要解决的新问题，发现了这个：
给定一个分数数组和一个整数 k。得分相同的玩家排名相同，玩家的排名为“得分高的玩家人数”+1。例如，给定scores = [10, 20, 20, 40]，对应的排名为[4, 2, 2, 1]。只有排名 <= k 的玩家才有资格进入下一轮。 Return 有资格进入下一轮的玩家数量。
我想出了一些方法来解决它，看来我能得到的最佳时间复杂度是 O(nlog(n))，算法如下：
- 对数组进行排序，时间复杂度O(nlogn)
- 然后，从 rank = 1 开始，每次我们传递到较低分数时更新它，所以当 rank <= k 时，不断增加符合条件的玩家数量，时间复杂度为 O(n ), 因为我们最终可能会遍历整个数组。
- return最终计数
另一个想法是创建一些哈希表，将得分作为键值，并将玩家数量作为值：
- 遍历数组，如果我们找到某个得分的人，则将另一个玩家添加到哈希表中该条目的值中，如果我们遇到的得分大于我们的最小得分哈希表，删除最小的分数条目，并放入新的分数（所以，到最后我们只有前 k 个分数）
- 然后将生成的哈希表中的所有值加在一起（或者，至少将相关条目加在一起，因为前 k 个分数并不一定意味着这些是排名前 k 的玩家，但我们知道只有前最多需要 k 个分数才能找到符合条件的数量）
这似乎有时间复杂度O(nk)，因为我们需要遍历整个数组，但每次检查当前k个分数的最小值，以确保我们只保留顶部k 分数。这通常需要比 O(nlogn) 更长的时间。
但是，我觉得一定有比我想出的方法更好的方法。有人有什么建议吗？
这里是原论坛post：https://leetcode.com/discuss/interview-question/1362837/goldman-sachs-new-analyst-2022-oa
另一种思路如下：
- 创建一个频率 table 来计算每个得分的玩家数量。这类似于您在 post 中提到的 hashtable 想法。键是唯一分数，值是该特定分数的玩家数量。
- 使用最小堆将频率为 table 的键推送到堆。一旦堆的长度变得等于
k，对于每次新的推入堆，从堆中弹出一个。这保证您最终在堆中获得k最大分数。 - 现在，遍历堆中的元素（不弹出），这些元素是 freq table 的键，然后将 table 中具有这些键的玩家数量相加。
时间复杂度方面，我们在 O(n) 中的初始数组上有 运行 来创建频率 table，我们已经从堆中推送和弹出不同分数的数量，并且因为在最坏的情况下不同分数的数量是 n，所以这使得它成为 O(n * log k) 操作。请注意，由于堆永远不会超过 k，因此它是 log k 而不是 log n。最后，我们遍历了堆中的 k 个元素，并从 freq table 中对它们的值求和，这是 k 操作。
所以，这变成了 n + (n * log k) + k，在大 O 术语中减少到 O(n * log k)。
这是选择问题的一个小变体：您正在寻找列表中第 k 个最小的元素，您需要输出的答案是小于或等于第 k 个元素值的值的数量。有很多可能的解决方案，但标准的是 Quickselect，它可以在线性 O(n) 时间内给出答案。让我们看看针对标准选择问题的各种越来越有效的方法，并查看它们的运行时间：
- 对数字进行排序，并计算最小的 k 个：运行时：
O(n log n). - 保留一个 min-heap，大小以 k 为界。遍历数组，将每个值推入堆中，并在大小达到 k+1 时弹出。运行时间：
O(n log k) - Min-Heapify整个数组，弹出k次。有时称为 'heapselect'。运行时间：
O(n + k log n) - 快速选择。通过随机枢轴选择，它具有
O(n)预期 run-time 和O(n^2)worst-case 运行时间，具有良好的平均性能。使用 median-of-medians 枢轴选择，它具有O(n)worst-case 运行时间，具有更高的常数因子。
如果你查看 C++ 标准库，在算法 header 中，此选择函数称为 第 n 个元素。 In practice, variants of quickselect are often used，例如 introselect 或 randomized-quickselect with heapselect fallback，它试图保留随机 QuickSelect 良好的平均性能但没有 O(n^2) worst-case.