Leetcode 347. 前 K 个高频元素

曾经终败给现在 2023-02-14 03:08 8阅读 0赞

### Leetcode 347. 前 K 个高频元素 ###

*  1、问题分析
 *  2、问题解决
 *  3、总结

# 1、问题分析 #

题目链接：[https://leetcode-cn.com/problems/top-k-frequent-elements/][https_leetcode-cn.com_problems_top-k-frequent-elements]  
  本质上就是一个 `map`使用的问题。代码我已经进行了详细的注释，理解应该没有问题，读者可以作为参考，如果看不懂(可以多看几遍)，欢迎留言哦！我看到会解答一下。

# 2、问题解决 #

笔者以`C++`方式解决。

#include "iostream"
    
    using namespace std;
    
    #include "algorithm"
    #include "vector"
    #include "queue"
    #include "set"
    #include "map"
    #include "string"
    #include "stack"
    
    
    class Solution { 
    private:
        // 定义一个map 保存 整数数组中的元素 和 该元素出现的次数
        map<int, int> dp_map;
        // 结果数组
        vector<int> result;
    
        // 简化类型
        typedef pair<int, int> PAIR;
    
        // 值比较函数
        bool static cmp_by_value(const PAIR &lhs, const PAIR &rhs) { 
            return lhs.second > rhs.second;
        }
    
    public:
        vector<int> topKFrequent(vector<int> &nums, int k) { 
            dealChen(nums, k);
            return result;
        }
    
        /** * 将整数数组，频率前 k 高的元素保存到 结果数组中 * @param nums * @param k */
        void dealChen(vector<int> &nums, int k) { 
            // 遍历整个数组
            for (int i = 0; i < nums.size(); ++i) { 
                // 首先查找 map 中是否存在该元素
                auto iterator1 = dp_map.find(nums[i]);
                // 如果存在
                if (iterator1 != dp_map.end()) { 
                    // 取出元素的个数并 + 1
                    iterator1->second += 1;
                }
                else { 
                    // 否则将该元素添加到map 容器中，初始化个数为 1
                    dp_map.insert(make_pair(nums[i], 1));
                }
            }
    
            // 将 map 转化成 vector 数组
            vector<PAIR> vec(dp_map.begin(), dp_map.end());
            dp_map.clear();
            // 按照值排序 （从大到小）
            sort(vec.begin(), vec.end(), Solution::cmp_by_value);
            int i = 0;
            //选取 前 k 个元素
            for (auto iter : vec) { 
                if (i >= k) { 
                    break;
                }
                // 保存到结果数组中
                result.push_back(iter.first);
                i++;
            }
    
        }
    };
    
    int main() { 
        vector<int> nums = {  1, 1, 1, 2, 2, 2, 2, 3 };
        Solution *pSolution = new Solution;
        auto vector1 = pSolution->topKFrequent(nums, 2);
        for (int i = 0; i < vector1.size(); ++i) { 
            cout << vector1[i] << " ";
        }
        cout << endl;
        system("pause");
        return 0;
    }

运行结果

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]  
有点菜，有时间再优化一下。

# 3、总结 #

难得有时间刷一波`LeetCode`, 这次做一个系统的记录，等以后复习的时候可以有章可循，同时也期待各位读者给出的建议。算法真的是一个照妖镜，原来感觉自己也还行吧，但是算法分分钟教你做人。前人栽树，后人乘凉。在学习算法的过程中，看了前辈的成果，受益匪浅。  
感谢各位前辈的辛勤付出，让我们少走了很多的弯路！  
哪怕只有一个人从我的博客受益，我也知足了。  
点个赞再走呗！欢迎留言哦！

[https_leetcode-cn.com_problems_top-k-frequent-elements]: https://leetcode-cn.com/problems/top-k-frequent-elements/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020053122124968.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3,size_16,color_FFFFFF,t_70