C + + Leetcode 347: 앞의 K 개 고주파 원소
1241 단어 C++LeetCode
예제 1: 입력: nums = [1, 1, 1, 2, 2, 3], k = 2 출력: [1, 2]
예제 2: 입력: nums = [1], k = 1 출력: [1]
설명: 주어진 k 가 항상 합 리 적 이 고 1 ≤ k ≤ 배열 에서 서로 다른 요소 의 개 수 를 가정 할 수 있 습 니 다.알고리즘 의 시간 복잡 도 는 O (n log n) 보다 높 아야 합 니 다. n 은 배열 의 크기 입 니 다.
사고 1. 하 쉬 맵.배열 요 소 를 map 에 넣 고 value 는 계산 을 표시 합 니 다.그리고 맵 을 value 에 따라 큰 것 에서 작은 것 으로 정렬 하고 마지막 으로 앞의 k 개의 요 소 를 배열 에 저장 합 니 다.
실현 방법 1. 해시 맵.
class Solution {
public:
vector topKFrequent(vector& nums, int k) {
unordered_map m;
vector res;
vector> temp;
for(int k:nums){ // map ,value
m[k]++;
}
for(auto it=m.begin();it!=m.end();++it){ // map value
temp.push_back(make_pair(it->first,it->second));
}
sort(temp.begin(),temp.end(),[](const pair &x,const pair &y)->int {
return x.second>y.second;
});
for(auto it=temp.begin();it!=temp.begin()+k;++it){ // , k
res.push_back(it->first);
}
return res;
}
};