Tag sort

LeetCode 692. Top K Frequent Words

Arunima Mandal Leave a comment

Problem link: https://leetcode.com/problems/top-k-frequent-words/

Note:

This is mainly a basic code for sorting a map according to its value. That can be done in multiple ways but I usually do that with the help of a vector, by copying the map into a vector of pairs, then sorting that vector by the second value of each pair.

Also, it’s a bit more challenging while sorting the vector since if the values are the same then the strings should be printed according to their lexicographical order.

Code:

class Solution {
public:
    static bool comp(pair<string,int> x, pair<string,int> y)
    {
        if(x.second>y.second) return 1;
        else if(x.second<y.second) return 0;
        else
        {
            int a=x.first.size();
            int b=y.first.size();
            for(int i=0; i<x.first.size(); i++)
            {
                if(x.first[i]<y.first[i]) return 1;
                else if(x.first[i]>y.first[i]) return 0;
            }
            if(a<b) return 1;
            else return 0; 
        }
        
    }
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> mp;
        vector<pair<string,int> > v;
        vector<string> ans;
        int sz=words.size();
        for(int i=0; i<sz; i++)
        {
            mp[words[i]]++;
        }
        
        unordered_map<string,int>:: iterator it;
        for(it=mp.begin(); it!=mp.end(); ++it)
        {
            v.push_back({it->first, it->second});
        }
        sort(v.begin(), v.end(), comp);
        for(int i=0; i<k; i++)
        {
            ans.push_back(v[i].first);
        }
        return ans;
    }
};