离散化

  离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率 

那么举个栗子,某个题目告诉你有1e5个数,每个数大小不超过1e9,要你对这些数进行操作(比如并查集之类的)。那么肯定不能直接开1e9大小的数组,但是1e5的范围就完全没问题。在举个栗子,现在对{4,7,6,9}进行离散化,那么得到的结果是{1,3,2,4},也就是说,当我们并不需要这些数据具体是多少时,就只需要知道他们的相对大小就行了。

 

 

离散化的方法有两种,一种是有重复元素的,一种是没有出现重复元素的。使用的时候务必要分清。

 

 

第一种:有重复元素的离散

 1 const int maxn = 2e6+6;
 2 
 3 int t[maxn],a[maxn];
 4 int n;
 5 
 6 int main(){
 7     scanf("%d",&n);
 8     for (int i=1;i<=n;i++){
 9         scanf("%d",&a[i]);
10         t[i] = a[i];
11     }
12     sort(t+1,t+1+n);
13     int size = unique(t+1,t+1+n)-t-1;
14     for (int i=1;i<=n;i++){
15         a[i] = lower_bound(t+1,t+1+size,a[i])-t;
16     }
17     for (int i=1;i<=n;i++){
18         printf("%d ",a[i]);
19     }
20     return 0;
21 }

 

第二种:无重复元素的离散


这种方式的离散复杂度比第一种优秀,但是不可以处理重复的元素

 1 const int maxn = 2e6+6;
 2 
 3 struct Node{
 4     int v,id;
 5     bool operator < (const Node a)const{
 6         return v < a.v;
 7     }
 8 }a[maxn];
 9 
10 int Rank[maxn],n;
11 
12 int main(){
13     scanf("%d",&n);
14     for (int i=1;i<=n;i++){
15         scanf("%d",&a[i].v);
16         a[i].id = i;
17     }
18     sort(a+1,a+1+n);
19     for (int i=1;i<=n;i++){
20         Rank[a[i].id] = i;
21     }
22     for (int i=1;i<=n;i++){
23         printf("%d ",Rank[i]);
24     }
25     return 0;
26 }

这种方法直接用结构体存储原本的数列的元素的位置,然后排序以后将他们再重新赋值。那么rank[]就是结构体a[]离散化后的结果。

  举个栗子:

  v: 3 6 5 10 8

  id:1 2 3 4 5

  排序以后:

  v: 3 5 6 8 10

  id:1 3 2 5 4

  所以离散化以后:

  v: 3 5 6 8 10

  id:1 3 2 5 4

  rk:1 2 3 4 5

  在按原来的顺序排列:

  v: 3 6 5 10 8

  rk:1 3 2 5 4

全部评论

相关推荐

昨天 23:26
河南大学 Java
双非本,刚学完Redis,项目只有外卖和点评,八股没准备,算法只有lqb省一,感觉敲的项目也是一言难尽没怎么吸收。怎么你们都有实习了
大牛之途:27急个锤子,你投日常实习最好的时间就是9,10月份,那时候暑期实习都结束了,正是缺人的时候。这份日常又能给你的暑期实习增加竞争力,暑期找的好了秋招也不怕了,都是环环相扣的
点赞 评论 收藏
分享
点赞 评论 收藏
分享
吐泡泡的咸鱼:我也工作了几年了,也陆陆续续面试过不少人,就简历来说,第一眼学历不太够,你只能靠你的实习或者论文或者项目经历,然后你没有论文,没有含金量高的比赛和奖项,只能看实习和项目,实习来说,你写的实习经历完全不清楚你想找什么工作?行研?数据分析?且写的太少了,再看项目,这些项目先不说上过大学读过研究生的都知道很水,然后对你想找的岗位有什么帮助呢?项目和实习也完全不匹配啊,你好像在努力将你所有的经历都放在简历里想表现你的优秀,但是对于你想找的岗位来说,有什么用呢?最后只能获得岗位不匹配的评价。所以你需要明白你想要找的岗位要求是什么,是做什么的,比如产品经理,然后再看你的经历里有什么匹配的上这个岗位,或者对这个岗位以及这个岗位所在的公司有价值,再写到你的简历上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务