0

I have a need to sort a Map(Key=Word,Value=CountofWord) in the descending order of the count of occurrences and print top 10 words in the Map. What can be the best possible method to do that?

My idea is to build a Multimap(Key=CountofWord,Values=Words) and then print the top 10 elements of the Multimap. But this would take O(n) extra space.

Can there be any other optimized solution?

Vishal R
  • 1,026
  • 1
  • 7
  • 21
  • Since maps are sorted by key, it doesn't seem like a bad or suboptimal solution to build a `map` instead. Sure, it needs `O(n)` space, but is it really that bad? If it really-really is (you know, you will have to do actual profiling to find it out!), then you can just iterate over the entire map and find the 10 most frequent words using the usual maximum search algorithm. – The Paramagnetic Croissant Oct 19 '14 at 08:11
  • @TheParamagneticCroissant It doesn't seem that there is any guarantee that the `int`s are unique. – Code-Apprentice Oct 19 '14 at 08:18
  • If space is an issue, you can build a min-heap of size 10. For each element, if it's larger than the heap minimum, pop the minimum and push the element. This will take O(nlogk) time and O(k) space, where k=10 here. – interjay Oct 19 '14 at 08:22

1 Answers1

0

Just to point out that your proposed solution does not take into account that two counts of word can have the same value, therefore two words would be mapped to the same key and override the last one.

What you could do instead is make a class of a word with member variables the word as string and the count as int, and implement the < operator to allow sorting of the objects by the std::sort method. Refer to http://www.cplusplus.com/reference/algorithm/sort/.

Memophysic
  • 147
  • 1
  • 6