Question: I have a vector with integers. I would like to select the most common numbers. I would like to make a top 5 list. For example:

```
std::vector<int> numbers = {32, 32, 32, 12, 12, 11, 11, 11, 9};

```

the most common numbers are: TOP 1: 32, TOP 2: 11, TOP 3: 12, TOP 4: 9;

after I selected them, I would like to store it into an other vector: the most common numbers.

Answer: 
Here's another algorithm, the cost is going to be O(n) for any `k`, plus a decent cache locality.

1.First store all elements in a `unordered_map` O(N)

```
std::unordered_map<int, int> m;
for(const auto ele: numbers) {
  m[ele]++;   
}

```

2.Dump all elements in a vector of pairs O(N) 

```
std::vector<std::pair<int, int>> temp;  
for(const auto& ele: m) {
 temp.emplace_back(ele.first ,  ele.second);   
}

```

3.Now use the nth\_element to find kth rank O(N) 

```
std::nth_element( temp.begin(), temp.begin()+k ,
temp.end(), [](const auto& p1, const auto& p2) {
        // Strict weak ordering
        if (p1.second > p2.second) {
            return true;
        }  if (p1.second < p2.second) {  
            return false;
        }
        return p1.first > p2.first; // We have to print large element first
    } );

```

4.Display the output

```
std::for_each( temp.begin(), temp.begin() +k - 1, [](const auto & p) {
    std::cout << p.first << " ";
});

```

[`Demo Here`](https://rextester.com/JIP26813)
You can create a `unordered_map<int,int> mp` where you can store the count of each number, like `mp[32] = 3`. 

Next you need to find the top five elements

1. **Time Complexity : O(mlogm)** : You can sort the map in descending order( to sort it you will have to use a extra vector), and take the first 5 elements.
2. **Time Complexity: O(m)** : Or you can iterate 5 times over the whole map to get the top file elements. Each time you iterate find the number with the greatest frequency which is not present in our topFive vector yet.

m : number of entries in the map.