2

I want to sort the elements in an array by their frequency.

Input: 2 5 2 8 5 6 8 8 

Output: 8 8 8 2 2 5 5 6

Now one solution to this would be:

  • Sort the elements using Quick sort or Merge sort. O(nlogn)
  • Construct a 2D array of element and count by scanning the sorted array. O(n)
  • Sort the constructed 2D array according to count. O(nlogn)

Among the other probable methods that I have read, one uses a Binary Search Tree and the other uses Hashing.

Could anyone suggest me a better algorithm? I know the complexity can't be reduced. But I want to avoid so many traversals.

4

1 回答 1

1

您可以对数组执行一次遍历而不对其进行排序，并在单独的结构上计算您找到元素的次数。如果您知道要找到的元素的范围，则可以在单独的数组上完成此操作，如果不知道，则可以在哈希表上完成。在任何情况下，这个过程都是 O(n)。然后，您可以使用每个元素关联的数量作为排序参数，执行生成的第二个结构（您有计数）的排序。正如您所说，如果您选择合适的算法，第二个过程就是 O(nlogn)。

对于第二阶段，我建议通过优先级队列使用堆排序。您可以告诉队列按 count 属性（在第一步计算的）对元素进行排序，然后将元素一一添加。添加完成后，队列已经排序，并且算法具有所需的复杂度。要检索您的元素，您只需开始弹出即可。

于 2013-06-24T07:23:04.023 回答