高级数据结构_学习的技术博客_51CTO博客

一、优先队列
二、图
三、前缀树
四、线段树
五、树状数组

本节的内容

一、优先队列

初始化大小为n的堆时间复杂度是O(n)

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

存储词频的最佳数据结构是哈希表，将单词和词频构成的对象构造出一个优先队列，解前k个的题目时，关键是看如何定义优先级别，以及优先队列的数据结构。

class Solution {
public:
vector topKFrequent(vector& nums, int k) {
unordered_map Map; //unordered_map：哈希表 map：红黑树
for(int i=0;i Map[nums[i]]++;
}
priority_queue,vector>,greater> > Q;
unordered_map::iterator it;
for(it=Map.begin();it!=Map.end();it++){
if(Q.size()==k){
if(it->second>Q.top().first){
Q.pop();
Q.push(make_pair(it->second,it->first));
}
}else{
Q.push(make_pair(it->second,it->first)); //第一个是频率，第二个是数字
}
}
vector res;
while(!Q.empty()){
res.push_back(Q.top().second);
Q.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
,int>();i++){>,>

三、前缀树

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

输入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]

输出: ["eat","oath"]