LeetCode刷题笔记-数据结构-day21

青旅半醒 2023-10-01 17:08 1阅读 0赞

#### 文章目录 ####

*  LeetCode刷题笔记-数据结构-day21
 *   *  451. 根据字符出现频率排序
     *   *  1.题目
         *  2.解题思路
         *  3.代码
     *  973. 最接近原点的 K 个点
     *   *  1.题目
         *  2.解题思路
         *  3.代码

## LeetCode刷题笔记-数据结构-day21 ##

### 451. 根据字符出现频率排序 ###

#### 1.题目 ####

> 原题链接：[451. 根据字符出现频率排序][451.]

![image-20220204091815935][]

#### 2.解题思路 ####

算法：小根堆

具体步骤：

1.  我们建立一个以`pair<int,int>`存储的小根堆，会以`pair`的第一个位置元素从小到大排序
2.  `pair`的第一个位置存储所有点距离原点的距离（这里为了方便直接用距离的平方代替）
3.  `pair`的第二个位置存储每个点所在数组的下标
4.  将所有点存入堆后，取出堆中前k个小的元素即可，得到他们的数组坐标，将其放入最终答案

#### 3.代码 ####

typedef pair<int,int> PII;
    class Solution {
        
    public:
        vector<vector<int>> kClosest(vector<vector<int>>& p, int k) {
        
            vector<vector<int>> res;
            priority_queue<PII, vector<PII>,greater<PII>> q;
            for(int i=0;i<p.size();i++){
        
                int t=p[i][0]*p[i][0]+p[i][1]*p[i][1];
                q.push({
        t,i});
            }
            while(k-->0){
        
                auto t=q.top();
                q.pop();
                res.push_back(p[t.second]);
            }
            return res;
        }
    };

### 973. 最接近原点的 K 个点 ###

#### 1.题目 ####

> 原题链接：[973. 最接近原点的 K 个点][973. _ K]

![image-20220204091901106][]

![image-20220204091914439][]

#### 2.解题思路 ####

算法：大根堆

具体步骤：

1.  我们建立一个以`pair<int,int>`存储的大根堆，会以`pair`的第一个位置元素从大到小排序
2.  `pair`的第一个位置存储每个字符出现的次数
3.  `pair`的第二个位置存储字符本身
4.  先用哈希表统计所有字符出现的次数，在加入大根堆中
5.  最后取出大根堆元素拼接字符串即可

#### 3.代码 ####

法一：

typedef pair<int,int> PII;
    class Solution {
        
    public:
        string frequencySort(string s) {
        
            map<char,int> hash;
            for(auto x:s) hash[x]++;
            priority_queue<PII, vector<PII>> q;
            for(auto [a,b]:hash) q.push({
        b,a});
            string res;
            while(q.size()){
        
                auto t=q.top();
                q.pop();
                res+=string(t.first,t.second);
            }
            return res;
        }
    };

法二：

class Solution {
        
    public:
        string frequencySort(string s) {
        
            unordered_map<char,int> cnt;
            for(auto x:s) cnt[x]++;
            sort(s.begin(),s.end(),[&](char a,char b){
        
               if (cnt[a] != cnt[b]) return cnt[a] > cnt[b];
                return a < b;
            });
            return s;
        }
    };

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[451.]: https://leetcode-cn.com/problems/sort-characters-by-frequency/
[image-20220204091815935]: https://img-blog.csdnimg.cn/img_convert/b6ff1abf89a0917394da647988ca2f26.png
[973. _ K]: https://leetcode-cn.com/problems/k-closest-points-to-origin/
[image-20220204091901106]: https://img-blog.csdnimg.cn/img_convert/c267e06a372587e16d9d369d9577eecf.png
[image-20220204091914439]: https://img-blog.csdnimg.cn/img_convert/51d9c7552f6cb89ccc1381ff5c8f632c.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/06cd315e4bd4461eb0f9b297090f83ab.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16