数据离散化详解 - 好文

一、概述

数据离散化是一个非常重要的思想。

为什么要离散化?当以权值为下标的时候，有时候值太大，存不下。所以把要离散化的每一个数组里面的数映射到另一个值小一点的数组里面去。

打个比方，某个题目告诉你有10^4个数，每个数大小不超过10^10，要你对这些数进行操作，那么肯定不能直接开10^10大小的数组，但是10^4的范围就完全没问题。

我们来看一下定义：离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。（by百度百科）

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：

原数据：1,999,100000,15；处理后：1,3,4,2；

原数据：{100,200}，{20,50000}，{1,400}；

处理后：{3,4}，{2,6}，{1,5}；

但是离散化仅适用于只关注元素之间的大小关系而不关注元素本身的值!

二、原理与操作

假如你只想简单操作一下，如求个逆序对什么的，那直接排序后将它的顺序覆盖回去就可以啦。（它不能去重）

假如你想写的更加专业就要采用以下步骤：

1、排序

2、去重

3、索引

首先我们要对所要进行离散化的数据进行排序：一般使用sort对数组或结构体排序。

然后是去重操作，为了写出高效的代码，我们需要复习两个STL函数：unique（）和lower_bound（），他们同时隶属于#include<algorithm>。

unique的作用是“去掉”容器中相邻元素的重复元素（不一定要求数组有序），它会把重复的元素添加到容器末尾（所以数组大小并没有改变），而返回值是去重之后的尾地址；

函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回
last的位置。【ps.upper_bound是返回第一个大于b[x]的指针，upper_bound（）=lower_bound（）+1】

关键代码如下：
int lsh[1000], lshcopy[1000], sy[1000]; int size=unique(sy,sy+n)-sy;
lsh[i]=lower_bound(sy,sy+size,lshcopy[i])-sy;
测试代码如下：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std;
int lsh[1000], lshcopy[1000], sy[1000];
//lsh[n]是即将被离散化的数组，lshcopy[n]是a[n]的副本，sy[n]用于排序去重后提供离散化后的值 int main() { int n;
scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&sy[i]); lshcopy[i]=sy[i]; }
sort(sy,sy+n);//第一步排序 for(int i=0;i<n;i++) { cout<<'('<<sy[i]<<')'; cout<<"\n";
} int size=unique(sy,sy+n)-sy;//unique显示去重后的个数 printf("size is : %d",size);
printf("\n"); for(int i=0;i<n;i++) {
lsh[i]=lower_bound(sy,sy+size,lshcopy[i])-sy; //即lsh[i]为lshcopy[i]离散化后对应的值
printf("lsh is : %d",lsh[i]); } }
方便理解，贴张图吧：

三、简单版

假如上面的你看的云里雾里，我决定更新一个简单版。
struct Node{ int val, order; }node[maxn]; for(int i=1; i<=n; i++) { if(i==1 ||
node[i].val!= node[i-1].val) { //去重 r[node[i].order] = i; } }
r数组负责收集结果。

热门工具换一换