联系我们contact

电 话:13902182895
联 系 人:张经理
地  址:天津市开发区第三大街豪威大厦1602
 

首页 > 新闻中心 > 离散化的思想和它的两种代码与区别

新闻中心

离散化的思想和它的两种代码与区别

    时间:2018-09-25


【转载】


离散化是什么:一些数字,他们的范围很大(0-1e9),但是个数不算多(1-1e5),并且这些数本身的数字大小不重要,重要的是这些数字之间的相对大小(比如说某个数字是这些数字中的第几小,而与这个数字本身大小没有关系,要的是相对大小)(6 8 9 4 离散化后即为 2 3 4 1)(要理解相对大小的意思)(6在这4个数字中排第二小,那么就把6离散化成2,与数字6本身没有关系, 8,9,4亦是如此)(2018.3.26 对这篇博客进行补充修改,被一道题的离散化卡到了,花了一晚上时间,才找到BUG(需离散化的数字有无相同的数字),黑体字为今晚对此篇博客进行了补充完善与区别)


离散化思想:因为数字太大,导致没有办法开那么大的数组,又因为数字个数并不多,这时候就可以对它们进行离散化,离散化是改变了数字的相对大小,例如,有500000个数字,他们的范围是0-1e9的,这样就满足离散化的条件。


就比如说,你可以开一个5e5的数组,但是你不能开一个1e9的数组。只改变这些数字的相对大小


 


第一种离散化。(包含重复元素,推荐使用)

离散化以前一直搞不懂是怎么实现的,看了一个代码才明白。



 

const int maxn=1e5+10;


int a[maxn], t[maxn];


int n;


scanf("%d",&n);


for(int i=1; i<=n; i++)


    scanf("%d",a[i]),t[i]=a[i];


sort(t+1,t+n+1);


m=unique(t+1,t+1+n)-t-1;//m为不重复的元素的个数


for(int i=1; i<=n; i++)


    a[i]=lower_bound(t+1,t+1+m,a[i])-t;


 


原来的a[i]离散化后成了后来的a[i];


离散化后的a[i]范围是(1-m);

举个栗子:

原序列:6 9 4 6 4

排序后:4 4 6 6 9

unique(元素去掉重复的)后:4 6 9 6 9  (前m位数字无重复,其他数字跟排序后的序列想比不改变)

unique有一个返回值,例如有十个有序的数列3 3 5 5 6 6 6 7 7 8,不重复的数字有五个,使用unique去重之后数列变成了3 5 6 7 8 6 6 7 7 8,它只改变了前五个数字后边的不变,返回值是 最后一个改变的数字的地址。so:m=unique(t+1,t+1+n)-t-1;一般要减去首地址(t+1),m为不重复的数字的个数


 


  第二种离散化(复杂度低,但是数据必须是无重复的才能使用)



 

struct A


{


int x, idx;


bool operator < (const A &rhs) const


{


return x < rhs.x;


}//也可以写个cmp函数排序


};


A a[MAXN];


int rank[MAXN];


int n;


scanf("%d",&n);


for(int i = 1; i <= n; ++i)


{


scanf("%d", &a[i].x);


a[i].idx = i;


}


//for(int i=1; i<=n; i++)


// printf("%d %d ",a[i].idx,a[i].x);


//printf(" ");


sort(a + 1, a + n + 1);


//for(int i=1; i<=n; i++)


// printf("%d %d ",a[i].idx,a[i].x);


//printf(" ");


for(int i = 1; i <= n; ++i)


{


rank[a[i].idx] = i;


// printf("rank[%d] = %d ",a[i].idx,i);


}


 


给你们个例子:

i      1 2 3 4

x     6 8 9 4

idx  1 2 3 4

排序后:


i      1 2 3 4  //离散化后的数字

x     4 6 8 9 

idx  4 1 2 3  //数字原来的所在的位置编号

将上面两行黑体数字对应起来 即是:rank[4]=1,rank[1]=2,rank[2]=3,rank[3]=4;  //rank[i]=j表示将原来在第i个位置上的数字离散化成j

so:

rank[1]=2;

rank[2]=3;

rank[3]=4;

rank[4]=1;

so:   6 8 9 4


就离散化为2,3,4,1

如果你想用原来的数字,就用排过序的结构体a[2]=6,a[3]=8,a[4]=9,a[1]=4; //a[i]=j表示排过序后现在的a数组里第i个数字的是j。j也就是第i小。

a[i]是原来的数字;

rank是离散化后的数字;


 


版权声明:觉得好的话就给他人分享一下吧,欢迎转载,码字不容易啊,转载麻烦注明出处 https://blog.csdn.net/xiangAccepted/article/details/73276826


 

上一篇:STM32 HAL库 定时中断和编码输入

下一篇:企业的根本目标及其内涵(一)

天津红翔吉瑞是天津市一家正规的天津软件开发公司,从事专业的软件开发业务

首页 公司简介 新闻中心 案例中心 联系我们
天津红翔吉瑞网络科技发展有限公司 版权所有 津ICP备16005209号-2   电话:13902182895 联系人:张经理   地址:天津市开发区第三大街豪威大厦1602