剑指offer57-61排序-堆
剑指 Offer II 057. 值和下标之差都在给定的范围内
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
题意两个数相减小于t，两个数下标小于k
思路1：滑动窗口和set
对于第一个条件abs(nums[i] - nums[j]) <= t，用一个滑动窗口维护
对于第二个条件 abs(i - j) <= k，将元素弄到有序，对于x，我想要满足abs(nums[x] - nums[j]) <= t ，那就是满足在x+t内或者在x-t内，也就是我想找目标在[x-t,x+t]范围内，因此先找比x-t大的第一个元素，然后元素存在并且小于x+t，就返回true
代码
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int n = nums.size();
set<int> rec;
for (int i = 0; i < n; i++) { //对于x，我想要满足abs(nums[x] - nums[j]) <= t ，那就是满足在x+t内或者在x-t内，也就是我想找目标在[x-t,x+t]范围内
auto iter = rec.lower_bound(max(nums[i], INT_MIN + t) - t);//那首先找比x-t大的第一个元素 这里lower_bound返回大于等于x-t的第一个位置
if (iter != rec.end() && *iter <= min(nums[i], INT_MAX - t) + t) {//如果目标元素存在并且小于x+t
return true;
}
rec.insert(nums[i]);//添加元素到滑动窗口
if (i >= k) {//如果滑动窗口满了
rec.erase(nums[i - k]);//去掉滑动窗口最前面的那个
}
}
return false;
}
};
剑指 Offer II 058. 日程表
有个日程安排，时间是前闭后开[10,23),添加时间，不要重复
方法： 使用map 键存start，值存end
class MyCalendar {
public:
map<int, int> cale; // cale[start] = end;
MyCalendar() {
cale[-1] = -1; // 避免 --it 越界
}
bool book(int start, int end) {
// 找到 end 之后的第一个日程, 即满足 start[idx] >= end 的第一个迭代器
auto it = cale.lower_bound(end);
// 检查前一个日程与当前日程是否重叠, 当end[idx - 1] <= start 时不重叠
if((--it)->second <= start){
cale[start] = end;
return true;
}
return false;
}
};
剑指 Offer II 059. 数据流的第 K 大数值
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
方法 使用堆
默认最大堆 ： priority_queue big_heap
最小堆 ： priority_queue<int, vector, greater> small_heap
最小堆经常用来求取数据集合中 k 个值最大的元素，而最大堆经常用来求取数据集合中 k 个值最小的元素
代码
class KthLargest {
private:
priority_queue<int, vector<int>, greater<int>> heap;
int size;
public:
KthLargest(int k, vector<int>& nums) {
size = k;
for (auto& num : nums) {
add(num);
}
}
int add(int val) {
if (heap.size() < size) {
heap.push(val);
}
else if (val > heap.top()) {
heap.pop();
heap.push(val);
}
return heap.top();
}
};
剑指 Offer II 060. 出现频率最高的 k 个数字
给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
方法一：使用堆
for循环输入数组，将各个元素出现频率更新到哈希表中，自定义一个小顶堆，小顶堆存放的是自定义数据类型，这个数据类型有两个值，小顶堆的比较的是比较的第二个值，然后遍历哈希表将元素添加到堆里面。
代码
class Solution {
public:
struct cmp {
bool operator() (const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second; // 最小堆，从小到大排序
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 哈希表统计数字出现频率
unordered_map<int, int> mp;
for (auto& num : nums) {
mp.count(num) ? mp[num]++ : mp[num] = 1;//如果unordered_map存在这个num键则对应的值+1否则赋值为1
}
// 最小堆
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> heap;
for (auto it = mp.begin(); it != mp.end(); ++it) { //遍历存放键值的unordered_map
if (heap.size() < k) { //如果堆还没有达到k 则一直添加（因为凑不齐前k大个元素）
heap.emplace(*it);
}
else if (it->second > heap.top().second) {//满了以后如果对应频率大于堆顶的频率
heap.pop(); //那么将其弹出
heap.emplace(*it); //并将本元素加入
}
}
// 返回结果
vector<int> ret(k, 0); //用一个vector存放结果
for (int i = k - 1; i >= 0; --i) {//for循环获取前k个值
ret[i] = heap.top().first;//存放top的键
heap.pop();//存放值
}
return ret;
}
};
剑指 Offer II 061. 和最小的 k 个数对
给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。
输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
第一个元素是第一个数组里的，第二个元素是第二个数组里的，返回前k个和最小的
方法一：枚举+最大堆
虽然可以枚举所有的情况，但是这样处理未考虑两个数组本身就是升序的特点，由于找k个，那么两个数组只遍历前k个就好了
class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
// 最大堆
auto cmp = [&](const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.first + lhs.second < rhs.first + rhs.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> heap(cmp);
for (int i = 0; i < nums1.size() && i < k; ++i) {
for (int j = 0; j < nums2.size() && j < k; ++j) {
if (heap.size() < k) {
heap.push({ nums1[i], nums2[j] });
}
else if (nums1[i] + nums2[j] < heap.top().first + heap.top().second) {
heap.pop();
heap.push({ nums1[i], nums2[j] });
}
}
}
int size = heap.size();
vector<vector<int>> ret(size, vector<int>(2, 0));
for (int i = 0; i < size; ++i) {
ret[size - 1 - i][0] = heap.top().first;
ret[size - 1 - i][1] = heap.top().second;
heap.pop();
}
return ret;
}
};