专栏首页SnailTyanLeetcode 347. Top K Frequent Elements

Leetcode 347. Top K Frequent Elements

版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn.net/Quincuntial/article/details/82117522

文章作者: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;
    }

};

Reference

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 867. Transpose Matrix

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Leetcode 870. Advantage Shuffle

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • Sum of Two Integers

    Tyan
  • leetcode 88 Merge Sorted Array

    Given two sorted integer arrays nums1 and nums2, merge nums2 intonums1 as one so...

    用户1539362
  • POJ 3041 Asteroids(匈牙利算法)

           题意就是有一个地图,然后给你几个点的坐标标记为'x',然后你有一个武器,每次可以消灭一行或一列的'x',问最少需要几次能把所有的'x'消灭完。然后...

    Ch_Zaqdt
  • C++版 - 剑指offer 面试题30:最小的K个数(topK问题) 题解

    题目: 输入n个整数,找出其中最小的k个数。例如:例如输入4 、5 、1、6、2、7、3 、8 这8 个数字,则最小的4 个数字是1 、2、3 、4

    Enjoy233
  • 牛客NOIP提高组R1 C保护(主席树)

    考虑一个点x,什么时候军队对它有贡献,肯定是u或v在他的子树内,且lca在他的子树外

    attack
  • Leetcode 867. Transpose Matrix

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • hdu1030

    @坤的
  • 洛谷P1966 火柴排队(逆序对)

    首先要保证权值最小,不难想到一种贪心策略,即把两个序列中rank相同的数放到同一个位置

    attack

扫码关注云+社区

领取腾讯云代金券