Leetcode 347. Top K Frequent Elements

Tyan

发布于 2019-05-26 10:45:14

3060

发布于 2019-05-26 10:45:14

文章被收录于专栏：SnailTyanSnailTyan

文章作者：Tyan

博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

Version 1

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

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> elements;
        for(int i = 0; i < nums.size(); i++) {
            elements[nums[i]]++;
        }
        vector<pair<int, int>> temp;
        map<int, int>::iterator iter;
        for(iter = elements.begin(); iter != elements.end(); iter++) {
            temp.push_back(pair<int, int>(iter->first, iter->second));
        }
        sort(temp.begin(), temp.end(), compare);
        vector<int> result;
        for(int i = 0; i < k; i++) {
            result.push_back(temp[i].first);
        }
        return result;
    }

};

Version 2

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> elements;
        for(int i = 0; i < nums.size(); i++) {
            elements[nums[i]]++;
        }
        vector<vector<int>> bucket(nums.size() + 1);
        map<int, int>::iterator iter;
        for(iter = elements.begin(); iter != elements.end(); iter++) {
            bucket[iter->second].push_back(iter->first);
        }
        reverse(bucket.begin(), bucket.end());
        vector<int> result;
        for(int i = 0; i < bucket.size(); i++) {
            for(int j = 0; j < bucket[i].size(); j++) {
                result.push_back(bucket[i][j]);
                if(result.size() == k) {
                    return result;
                }
            }
        }
        return result;
    }

};