LeetCode 347. Top K Frequent Elements

The link : https://leetcode.com/problems/top-k-frequent-elements/

Top K Frequent Elements - LeetCode

문제 요약

1. 배열 nums[]에서 가장 많이 사용된 숫자를 k개 만큼 나열합니다.

2. 이때 k개의 숫자들은 어떠한 순서로 나열되도 상관없습니다.

 

핵심 포인트

 

알고리즘의 시간 복잡도는 O(n log n) 이하여야 합니다.

 

문제 풀이

 

1. nums 배열에서 가장 많이 사용된 원소를 파악하기 위한 map<int,int>와 정답 벡터를 선언합니다.

        vector<int> ans;
        map<int, int> m;

 

2. nums배열의 원소에 따라 해당 key값에 value를 증가시킵니다.

그리고 pair<int,int>형 벡터를 선언하여 해당 벡터에 map을 복사합니다.

        for(int i=0; i<nums.size(); i++) m[nums[i]]++;
        vector<pair<int,int>> v(m.begin(),m.end());

 

3. 배열을 정렬합니다. 이때 정렬 기준은 v[i].second가 더 큰 값이 먼저 오게 됩니다.

    static bool comp(const pair<int,int> &a, const pair<int,int> &b){
        return (a.second>b.second);
    }    

// main함수 내부

sort(v.begin(),v.end(),comp);

 

4. k개 만큼 가장 빈번히 사용된 숫자를 ans벡터에 저장하고, ans 벡터를 반환합니다.

        for(int i=0; i<k; i++) ans.push_back(v[i].first);
        return ans;

 

class Solution {
public:
    static bool comp(const pair<int,int> &a, const pair<int,int> &b){
        return (a.second>b.second);
    }    
    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> ans;
        map<int, int> m;
        for(int i=0; i<nums.size(); i++) m[nums[i]]++;
        vector<pair<int,int>> v(m.begin(),m.end());
        sort(v.begin(),v.end(),comp);
        for(int i=0; i<k; i++) ans.push_back(v[i].first);
        return ans;
    }
};