离散化
- 在不改变数据相对大小的前提下, 对数据进行相应的缩小.
- 可以有效降低时空复杂度.
- 应用于空间不够的情况, 数据本身过大无法作为下表的情况.
- 且只与数据之间相对大小有关, 具体是多少无关.
使用 STL 进行离散化
- 思路: 排序, 删除重复元素, 索引元素离散化后的值.
- 实现:
- for(int i=1;i<=n;i++) {
- cin>>A[i];
- B[i]=A[i];
- }
- sort(B+1,B+1+n);
- cnt=unique(B+1,B+1+n)-B-1;
- for(int i=1;i<=n;i++)
- A[i]=lower_bound(B+1,B+1+cnt,A[i])-B;
本文章未完, 持续更新
离散化
来源: http://www.bubuko.com/infodetail-3129278.html