算法小结|基础算法——离散化算法|离散化

手动实现离散化 1 主要功能：

离散化主要是通过建立一个映射，将分散的元素的位置映射成连续的位置以节约空间。

2 原理（代入具体示例来说明）：

文章图片

说明： X为题目要进行操作的数组元素的下标，Y为经过离散化后的下标。
原理：

若不离散化，则针对该例需要开一个大小为9000000的数组保存操作结果！
通过建立一个映射数组来存储所有要进行操作的下标X，然后将其排序去重，每次操作X位置元素时用二分法查找X在映射数组中的位置Y。操作X位置元素改为操作Y位置元素。
排序是为了方便二分查找，排序后去重比较方便，去重是为了建立X与Y的一一映射，不去重则会导致一个X可以对应多个Y（可以不去重，每次查询X只返回特定的Y就行了，但是这样时间复杂度更慢，所以最好还是去重）。
离散化后只需要开大小为X的个数的数组了，针对本例我们只需开一个大小为5的数组即可。
离散化也有缺点，就是它排序去重需要nlogn的时间，每次操作要用logn倍直接操作的时间。

3 代码示例

//题目要求对输入位置的元素进行加1操作，操作结束后输出按顺序输出所有输入位置的结果（输入位置可能重复） #include #include #includeusing namespace std; const int N = 2e5 + 5; int n, a[N], cnt[N]; vectoralls; //二分实现原位置X映射到映射位置Y int find(int 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 l; }int main() { cin >> n; for(int i = 0; i < n; i++) { scanf("%d", &a[i]); alls.push_back(a[i]); //将所有要操作的下标存入映射数组alls中 } sort(alls.begin(), alls.end()); //排序 alls.erase(unique(alls.begin(), alls.end()), alls.end()); //去重 for(int i = 0; i < n; i++) cnt[find(a[i])]++; //操作原位置映射位置的结果数组 for(int i = 0; i < n; i++) cout << cnt[find(a[i])] << ' '; //输出原位置映射位置的结果数组 return 0; }

4 经典例题 【算法小结|基础算法——离散化】1.模板题：Acwing103.电影、AcWing 802. 区间和
5 其他方式实现离散化 1.利用map和unordered_map，使用之前都要导入相应头文件。