算法基础学习笔记——⑤离散化\区间和并

命运之光

发布于 2024-03-20 10:54:38

1350

发布于 2024-03-20 10:54:38

文章被收录于专栏：我在本科期间写的文章

✨博主：命运之光 ✨专栏：算法基础学习

前言：算法学习笔记记录日常分享，需要的看哈O(∩_∩)O，感谢大家的支持！

✨简述

离散化是一种辅助解决问题的操作，当问题中涉及的数据范围非常大，但是实际使用到的数据是比较少的。并且问题的求解是和它范围里的其它数据有关系的，那么可以将这些可能使用到的数据放到一起，排序去重，就将它们映射到了一个新的较小的范围里。

例如，下面几个数是在(−∞,∞)范围里的，实际用到的数：

6 、 − 10000 、 114514 、 1919 、 − 123 、 1919

排序之后变成：

− 10000 、 − 123 、 6 、 1919 、 1919 、 114514

去重之后变成：

− 10000 、 − 123 、 6 、 1919 、 114514

它在数组中的下标即可对应于一种离散化结果：

0 、 1 、 2 、 3 、 4

在有些问题（比如下面涉及前缀和操作的问题）里，需要下标从1开始，所以离散化结果也常常用从1开始的：

1 、 2 、 3 、 4 、 5

特指整数离散化

🍓离散化模板：

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
     int l = 0, r = alls.size() - 1;
     while (l < r)
     {
         int mid = l + r >> 1;
         if (alls[mid] >= x) r = mid;
         else l = mid + 1;
     }
     return r + 1; // 映射到1, 2, ...n
}

✨区间和并

很多区间如果有交集就把它们合并为一个区间

🍓区间和并模板：

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
     vector<PII> res;
     sort(segs.begin(), segs.end());
     int st = -2e9, ed = -2e9;
     for (auto seg : segs)
         if (ed < seg.first)
         {
             if (st != -2e9) res.push_back({st, ed});
             st = seg.first, ed = seg.second;
         }
         else ed = max(ed, seg.second);
     if (st != -2e9) res.push_back({st, ed});
     segs = res;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-05-27，如有侵权请联系 cloudcommunity@tencent.com 删除

数据