LeetCode 347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

分析：先遍历数组将数组的值与出现的次数用map映射，因为根据map的值来排序，所以用pair<int, int>类型的vector转存后用sort实现排序方法。从大到小排序，然后取前k个值储存在新的vector v中返回v。

typedef pair<int, int> PAIR;
class Solution {
public:
    static int cmp(const PAIR &x, const PAIR &y) {  
        return x.second > y.second;  
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> v;
        map<int, int> m;
        vector<PAIR> pair_vec;
        for(int i = 0; i < nums.size(); i++) {
            m[nums[i]]++;
        }
        for(map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
            pair_vec.push_back(make_pair(it->first, it->second));
        }
        sort(pair_vec.begin(), pair_vec.end(), cmp);
        vector<PAIR>::iterator curr = pair_vec.begin();
        while(k--) {
            v.push_back(curr->first);
            curr++;
        }
        return v;
    }
};

typedef pair<int, int> PAIR;

class Solution {

public:

static int cmp(const PAIR &x, const PAIR &y) {

return x.second > y.second;

}

vector<int> topKFrequent(vector<int>& nums, int k) {

vector<int> v;

map<int, int> m;

vector<PAIR> pair_vec;

for(int i = 0; i < nums.size(); i++) {

m[nums[i]]++;

}

for(map<int, int>::iterator it = m.begin(); it != m.end(); it++) {

pair_vec.push_back(make_pair(it->first, it->second));

}

sort(pair_vec.begin(), pair_vec.end(), cmp);

vector<PAIR>::iterator curr = pair_vec.begin();

while(k--) {

v.push_back(curr->first);

curr++;

}

return v;

}

};

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版