347. Top K Frequent Elements

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

Top K Frequent Elements - LeetCode

! 시간 복잡도는 O(nlogn) 이하여야 함

---

SOLUTION CODE

# PYTHON

● Count 를 이용한 풀이 

from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Counter({1: 3, 2: 2, 3: 1})
        c=Counter(nums)
        # count숫자 가져오기
        res = c.most_common(k)

        return [num[0] for num in res]

 

# cf_simple ver
def topKFrequent(nums, k):
	return [x[0] for x in Counter(nums).most_common(k)]

● Bucket sort

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        freq = [[] for i in range(len(nums) + 1)]
        for n in nums: # count[원소] = frequent
            count[n] = 1 + count.get(n,0)
        for n, c in count.items(): # bucket sort
            freq[c].append(n)
        res = []
        for i in range(len(freq) - 1, 0, -1): # 배열끝부터 앞으로 검사
            for n in freq[i]:
                res.append(n)
                if len(res) == k:
                    return res

 

 

# C++

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> res; // 정답
        map<int,int> count_em; // count_em[원소] = 카운트

        for(int i=0; i<nums.size(); i++)
            count_em[nums[i]]++; // 해당 key값에 value증가

        //map ->vector에 복사
        vector<pair<int,int>> v(count_em.begin(),count_em.end());

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

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


    }
};

 

---

● Count 의 시간 복잡도는 O(N)

● Bucket sort

- input array size가 한정되어있을때 주로 사용하며,시간복잡도는 O(N)

- Bucket array size = input array size

ex)[1, 1, 1, 2, 2, 100]

i(count)	0	1	2	3	4	5	6
values		[100]	[2]	[1]

 

● Map / vector 차이를 정리해보았다.

#include <map>
#include <vector>

using namespace std;

int main(){
	map<string,int> m;
	vector<int> v;
	
	//요소 추가 ***
	
	//m
	m.insert(make_pair("key",1));
	m["key2"] = 2;
	
	//v
	v.push_back(1);
	vector <string> v2 {"vector","practice"};
	
	//map->vector copy ***
	// 선언 뒤 복사
	vector<pair<string,int> vector_c(m.size())>;
	copy(m.begin(), m.end(), vector_c.begin());
	
	// 선언 + 복사
	vector<pair<string,int>vector_c1(m.begin(),m.end())>;
	
	//map->map copy
	map<string,int> mapTarget;
	if(0<m.size()){
		std::copy(m.begin(),m.end(), std::inserter(mapTarget,maTarget.begin()));
	}
	
}

● compare

-"왼쪽이 오른쪽보다" 가 기준임

bool compare(int a,int b){ return a>b } //내림차순 정렬