// 定义一个vector<int>类型的变量alls,用于存储所有待离散化的值
vector<int> alls;
// 对所有值进行排序,使用sort函数将其升序排列。
sort(alls.begin(), alls.end());
// 去掉重复元素,使用erase和unique函数将相邻且相等的元素去掉。
alls.erase(unique(alls.begin(), alls.end()), alls.end());
// 实现一个二分查找函数find,用于找到x对应的离散化后的值。
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
// 不断执行二分查找操作,在每次迭代中计算出中间位置mid,
// 并判断alls[mid]是否大于等于x。如果是,则将右指针r更新为mid;
// 否则将左指针l更新为mid+1。
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
// 最终返回r+1作为x对应的离散化后的值。
return r + 1;
}
这段代码实现了一种常见的离散化算法,用于将一些连续或者离散的数值映射到一个有限的区间内,以便于后续处理。具体来说,该算法包含以下几个步骤:
定义一个vector<int>
类型的变量alls
,用于存储所有待离散化的值。
对所有值进行排序,使用sort
函数将其升序排列。
去掉重复元素,使用erase
和unique
函数将相邻且相等的元素去掉。
实现一个二分查找函数find
,用于找到x
对应的离散化后的值。在该函数中,定义两个指针l
和r
,并初始化为0
和n-1
。然后不断执行二分查找操作,在每次迭代中计算出中间位置mid
,并判断alls[mid]
是否大于等于x
。如果是,则将右指针r更新为mid
;否则将左指针l更新为mid+1
。最终返回r+1
作为x
对应的离散化后的值。
整个过程可以看做是把原始数据集合映射到一个从1开始连续递增的整数序列上,方便进行后续处理。