剑指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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

剑指 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;      
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

剑指 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 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();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

剑指 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

剑指 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

方法二：a1，b1,被选中下一个一定是a2，b1