Leetcode 692. 앞의 K 고주파 단어 [재 부팅 비교 연산 자]

글 목록
문제 설명
문제 풀이 보고서
실현 코드
참고 자료
문제 설명
비어 있 지 않 은 단어 목록 을 주 고 가장 많이 나 온 k 개의 단 어 를 되 돌려 줍 니 다.
돌아 오 는 답 은 단어의 출현 빈도 에 따라 높 은 것 에서 낮은 것 으로 정렬 해 야 한다.만약 서로 다른 단어 가 같은 출현 주파 수 를 가지 고 있다 면 알파벳 순서에 따라 정렬 해라.
예시 1:
입력: [i "," love "," leetcode "," i "," love "," coding "], k = 2 출력: [i", "love"] 해석: "i" 와 "love" 는 가장 많이 나타 난 두 단어 로 모두 2 회 입 니 다.알파벳 순 으로 'i' 는 'love' 전에 주의 하 세 요.
예시 2:
입력: ["the", "day", "is", "Sunny", "the", "the", "Sunny", "is", "is", "is"], k = 4 출력: ["the", "is", "Sunny", "day"] 해석: "the", "is", "Sunny" 와 "day" 는 가장 많이 나 온 네 단어 로 4, 3, 2, 1 회 순 으로 나 타 났 다.
주의:
k 총 유효 치, 1 ≤ k ≤ 집합 원소 수 를 가정 합 니 다.입력 한 단 어 는 모두 소문 자로 구성 되 어 있다.
확장 연습:
O (n log k) 시간 복잡 도와 O (n) 공간 복잡 도로 해결 하려 고 시도 합 니 다.
출처: 리 트 코드 링크: 저작권 은 리 트 코드 네트워크 의 소유 입 니 다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
문제 풀이 보고서
두 가지 해법.첫 번 째 시간 복잡 도 는 O (n l o g n) O (nlogn) O (nlogn) 두 번 째 시간 복잡 도 는 O (n l o g k) O (nlogk) O (nlogk) O (nlogk) 두 번 째 방법 에서 크기 를 다시 불 러 와 연산 자 를 판단 하 는 방법 에 주의해 야 한다.
구현 코드

// class Solution {
// public:
//     static bool cmp(paira, pairb){
//         if(a.second!=b.second)
//             return a.second>b.second;//             
//         else return a.first
//     }
//     vector topKFrequent(vector& words, int k) {
//         unordered_mapmp;
//         vectorans;
//         for(int i=0;i
//             mp[words[i]]++;
//         }
//         vector>vec;
//         for(auto m:mp){
//             vec.push_back({m.first, m.second});
//         }
//         sort(vec.begin(), vec.end(), cmp);
        
//         for(int i=0;i
//             ans.push_back(vec[i].first);
//         }
        
//         return ans;
//     }
// };

typedef pair<int,string> P;//  ，  

struct Order
{//  greater   ，  a      b ，  true
    bool operator()(const P& a,const P& b)const
    {//a,b    ，    ，    ，         .
        return (a.first>b.first||(a.first==b.first&&a.second<b.second));
    }
};

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> ans;
        int n=words.size();
        Order ord;//   

        //      
        unordered_map<string,int> word_freq;
        //      
        for(string x:words)word_freq[x]++;

        //  ，       k    ，       O(logk) ，     O(nlogk) 
        priority_queue<P,vector<P>,Order> pq;

        for(auto item:word_freq)
        {
            P tmp{item.second,item.first};//    
            //         
            if(pq.size()<k)pq.push(tmp);
            //           >=k
            else if(ord(tmp,pq.top()))
            {//  tmp    >      
                pq.push(tmp);
                pq.pop();//pop   ，        ,     k   
            }    
        }

        // k         
        while(k--)
        {
            ans.push_back(pq.top().second);
            pq.pop();
        }
        reverse(ans.begin(),ans.end());//O(k)    

        return ans;
    }
};

//   ：ydong17
//   ：https://leetcode-cn.com/problems/top-k-frequent-words/solution/wei-hu-da-xiao-wei-kde-xiao-ding-dui-ji-ke-onlogk-/
//   ：  （LeetCode）
//         。             ，          。

참고 자료
[1] Leetcode 692. 앞의 K 고주파 단어 [2] 문제 풀이 구역: ydong 17