vector<int> topKFrequent(vector<int>& nums, int k) {
if(k==nums.size())
return nums;
map<int,int> mp;
for(int i=0;i<nums.size();i++)
mp[nums[i]]++;
multimap<int,int> m;
for(auto& it:mp){
m.insert({it.second,it.first});
}
vector<int> ans;
for (auto itr = m.crbegin(); itr != m.crend(); ++itr){
ans.push_back(itr->second);
if(ans.size()==k)
break;
}
return ans;
}
I am using multimap to sort the map by values.I don't understand if I use priority queue which time complexity is better ? using priority_queue or using multimap? Can anyone explain?
In my opinion you have not the optimal solution.
You use a std::map instead of a std::unordered_map. That will have a higher complexity in most cases. std::maphas logarithmic complexity, std::unordered_map has on average constant-time complexity.
The std::multimap is not needed at all. It will add unneccessary space and time complexity (Logarithmic). A std::priority_queuehas constant time lookup, but logarithmic insertion. So, could be better than the std::multimapin your case.
The most efficient solution would be to use a std::unordered_map and then std::partial_sort_copy. The complexity for this is O(N·log(min(D,N)), where N = std::distance(first, last), D = std::distance(d_first, d_last) applications of cmp. (Taken from CPPReference).
A somehow generic C++17 example solution could be the below:
#include <iostream>
#include <utility>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <iterator>
#include <type_traits>
// Helper for type trait We want to identify an iterable container ----------------------------------------------------
template <typename Container>
auto isIterableHelper(int) -> decltype (
std::begin(std::declval<Container&>()) != std::end(std::declval<Container&>()), // begin/end and operator !=
++std::declval<decltype(std::begin(std::declval<Container&>()))&>(), // operator ++
void(*std::begin(std::declval<Container&>())), // operator*
void(), // Handle potential operator ,
std::true_type{});
template <typename T>
std::false_type isIterableHelper(...);
// The type trait -----------------------------------------------------------------------------------------------------
template <typename Container>
using is_iterable = decltype(isIterableHelper<Container>(0));
// Some Alias names for later easier reading --------------------------------------------------------------------------
template <typename Container>
using ValueType = std::decay_t<decltype(*std::begin(std::declval<Container&>()))>;
template <typename Container>
using Pair = std::pair<ValueType<Container>, size_t>;
template <typename Container>
using Counter = std::unordered_map<ValueType<Container>, size_t>;
// Function to get the k most frequent elements used in any Container ------------------------------------------------
template <class Container>
auto topKFrequent(const Container& data, size_t k) {
if constexpr (is_iterable<Container>::value) {
// Count all occurences of data
Counter<Container> counter{};
for (const auto& d : data) counter[d]++;
// For storing the top k
std::vector<Pair<Container>> top(k);
// Get top k
std::partial_sort_copy(counter.begin(), counter.end(), top.begin(), top.end(),
[](const Pair<Container>& p1, const Pair<Container>& p2) { return p1.second > p2.second; });
return top;
}
else
return data;
}
int main() {
std::vector testVector{ 1,2,2,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,6,7 };
for (const auto& p : topKFrequent(testVector, 2)) std::cout << "Value: " << p.first << " \t Count: " << p.second << '\n';
std::cout << '\n';
double cStyleArray[] = { 1.1, 2.2, 2.2, 3.3, 3.3, 3.3 };
for (const auto& p : topKFrequent(cStyleArray, 2)) std::cout << "Value: " << p.first << " \t Count: " << p.second << '\n';
std::cout << '\n';
std::string s{ "abbcccddddeeeeeffffffggggggg" };
for (const auto& p : topKFrequent(s, 2)) std::cout << "Value: " << p.first << " \t Count: " << p.second << '\n';
std::cout << '\n';
double value = 12.34;
std::cout << topKFrequent(value, 2) << "\n";
}