我想按频率对数组中的元素进行排序。
Input: 2 5 2 8 5 6 8 8
Output: 8 8 8 2 2 5 5 6
现在一个解决方案是:
- 使用快速排序或合并排序对元素进行排序。 O(nlogn)
- 构造一个二维元素数组，并通过扫描排序后的数组进行计数。 O(n)
- 根据计数对构建的二维数组进行排序。 O(nlogn)
在我读过的其他可能方法中，一种使用二叉搜索树，另一种使用哈希。
谁能建议我一个更好的算法？我知道复杂性无法降低。但是我想避免这么多遍历。
最佳答案
您可以在数组上执行一次而不对其进行排序，然后在一个单独的结构上计算您找到一个元素的次数。这可以在单独的数组上完成，如果您知道您将找到的元素的范围，或者如果您不知道，则可以在哈希表上完成。在任何情况下，这个过程都是 O(n)。然后，您可以执行生成的第二个结构(您有计数)的排序，使用每个元素关联的数量作为排序参数。如果您选择合适的算法，第二个过程就像您所说的 O(nlogn)。
对于第二阶段，我建议通过优先级队列使用堆排序。您可以告诉队列按计数属性(在第一步中计算的那个)对元素进行排序，然后将元素一个接一个地添加。添加完成后，队列已经排序，算法具有所需的复杂度。要按顺序检索元素，您只需开始弹出即可。
关于arrays - 按频率排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17269840/