数据结构 结构体:离散化基础解题图路与题解代码

arkfactor 初赛笔试题 3596 2910
不断提升技能,才能在职场中立于不败之地!全网最全C++题库,助您成为编程领域的佼佼者。
1. 离散化简介    离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率,通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小,    离散化本质上可以看成是一种哈希,其保证数据在哈希以后仍然保持原来的全/偏序关系,    当有些数据因为本身很大或者类型不支持,自身无法作为数组的下标来方便地处理,而影响最终结果的只有元素之间的相对大小关系时,我们可以将原来

1. 离散化简介

    离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。
    离散化本质上可以看成是一种哈希,其保证数据在哈希以后仍然保持原来的全/偏序关系。
    当有些数据因为本身很大或者类型不支持,自身无法作为数组的下标来方便地处理,而影响最终结果的只有元素之间的相对大小关系时,我们可以将原来的数据按照从大到小编号来处理问题,即离散化。
    本文针对 整数、有序数组 进行离散化。

2.为什么要进行离散化处理?

    离散化是程序设计中一个常用的技巧,它可以有效的降低时间复杂度。
    其基本思想就是在众多可能的情况中,只考虑需要用的值。离散化可以改进一个低效的算法,甚至实现根本不可能实现的算法。

3. 举例说明

    有一个数组 a[] ,包含 1、3、100、2000、50000,五个数,将其对应映射到 0、1、2、3、4,的过程就叫做离散化。

4. 离散化过程中的问题

    数组 a[] 当中可能存在重复的元素,对此,我们需要 去重。
    如何算出 a[n] 离散化后的值,对此,我们可以使用 二分法 。具体见前文 整数二分

 

#include<bits/stdc++.h>
using namespace std;
struct sadbee__
{
    int sz,xh,px;
}a[10001];
bool sadbee(sadbee__ a,sadbee__ b)
{
    return a.sz<b.sz;
}
bool sadbee2(sadbee__ a,sadbee__ b)
{
    return a.xh<b.xh;
}
int main()
{
    int n,m,i,j;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i].sz;
        a[i].xh=i;
    }
    sort(a+1,a+n+1,sadbee);
    for(i=1;i<=n;i++)
    {
        a[i].px=i;
    }
    sort(a+1,a+n+1,sadbee2);
    for(i=1;i<=n;i++)
    {
        cout<<a[i].px<<" ";
    }
    return 0;
}
数据结构 结构体:离散化基础解题图路与题解代码-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
成为编程大师,不再是梦想!全网最全C++题库,助您开启编程新篇章。

发布评论 2910条评论)

评论列表

2024-07-07 01:39:08

我对楼主的敬仰犹如滔滔江水绵延不绝!http://pn1.06gk.cn

2024-07-07 02:22:19

收藏了,怕楼主删了!http://89jgx.bnsrqrz.cn

2024-07-07 07:51:42

楼主的等级很高啊!http://nu2.dpgljks.cn

2024-07-08 10:45:44

谢谢楼主的分享!http://btzr.chifengzj.com

2024-07-09 02:10:59

最近回了很多帖子,都没人理我!http://5rv.szhuangtongbang.com

2024-07-09 02:28:19

缺乏激情了!http://www.snjunying.com

2024-07-09 06:23:40

坚持回帖!http://www.yanghongchang.com

2024-07-09 06:37:53

支持一下!http://0ukf8.lqbsxaf.cn

2024-07-09 08:03:17

楼主的头像是本人吗?http://m.chifengzj.com

2024-07-09 08:12:40

楼主你想太多了!http://m.snjunying.com

2024-07-09 09:49:56

顶顶更健康!https://www.ejy365.com/jygg_more

2024-07-09 10:32:25

世界末日我都挺过去了,看到楼主我才知道为什么上帝留我到现在!http://l8800.szhuangtongbang.com

2024-07-09 11:34:35

十分赞同楼主!http://949.szhuangtongbang.com

2024-07-09 11:35:12

楼主你想太多了!http://g19.fsdcsl.com

2024-07-09 13:54:05

态度决定一切,不错!http://www.zjchuzhou.com

2024-07-09 15:44:41

顶一个!http://k77pxc.szhuangtongbang.com

2024-07-09 17:24:23

有钱、有房、有车,人人都想!http://z89u.scu-sh.cn

2024-07-09 17:30:09

这篇文章真是让人受益匪浅!http://w8g34c.xibili.com

2024-07-09 18:01:33

顶一个!http://wap.tjjixi.com

2024-07-09 19:42:17

网站做得不错http://www.nnsogou.com

2024-07-09 19:52:28

观点鲜明,立场坚定,作者态度明确。http://mobile.snjunying.com

2024-07-09 21:28:18

不是惊喜,是惊吓!http://y8df5v.xibili.com

2024-07-09 21:47:59

祖国尚未统一,我却天天灌水,好内疚!http://cmo4f6.scu-sh.cn

2024-07-10 02:10:17

我裤子脱了,纸都准备好了,你就给我看这个?http://lfe1u.yxshopping.com/00/4.html

2024-07-10 02:11:28

学习雷锋,好好回帖!http://y549c.clwclwc.com

2024-07-10 10:20:58

我只看看不说话。。。http://hx3.gujinghotel.com

2024-07-10 10:33:25

有内涵!http://ac2r.jlno1.com

2024-07-10 14:19:48

好东西,学习学习!http://31kdo.scu-sh.cn

2024-07-10 16:11:10

楼主人气很旺!http://pnz7s.scu-sh.cn

2024-07-10 17:48:28

看了这么多帖子,第一次看到这么经典的!http://hs6q.gujinghotel.com

2024-07-10 18:15:13

听楼主一席话,省我十本书!http://qu7zs3.scu-sh.cn

2024-07-10 19:23:09

大神就是大神,这么经典!http://697u.xibili.com

2024-07-10 19:55:08

楼主最近很消极啊!http://hyk.scu-sh.cn

2024-07-10 20:07:22

东方不败外加灭绝师太啊!http://ya47h3.scu-sh.cn

2024-07-11 04:24:19

这一年啥事没干,光研究楼主的帖子了!http://gk13h.itreeinn.com

2024-07-11 04:37:07

楼主该去看心理医生了!http://84etfb.lyjtel.com

2024-07-11 12:24:59

坚持回帖!http://md8kz.lszn1988.com/t/4.html

2024-07-11 13:08:57

我回帖楼主给加积分吗?http://57c.bljzq.com

2024-07-11 13:10:19

信楼主,考试不挂科!http://eow38d.bljzq.com

2024-07-11 13:15:21

这么好的帖子,应该加精华!http://nci0.wzyuqi.com

2024-07-11 13:33:01

没人理我,好伤心啊!http://io4.gongjuyou.com

2024-07-11 13:50:12

缺乏激情了!http://tn7.hisensev.com

2024-07-11 15:11:47

十分赞同楼主!http://hus4o9.110celulares.com

2024-07-11 15:23:00

好好学习楼主的帖子!http://ggfwvm.longkangys.com.cn

2024-07-11 15:34:42

楼上的说的很多!http://g3wx.zjcgdz.com

2024-07-11 16:02:18

没人理我,好伤心啊!http://gu9c0.goldeasycloud.com

2024-07-11 16:04:42

林子大了,什么鸟都有了啊!http://df26d.ningbotour.com

2024-07-11 16:16:42

楼主的头像能辟邪啊!http://www.2qukuai.com

2024-07-11 16:26:07

我只看看不说话。。。http://uw57w.qqw16.com

2024-07-11 17:01:03

看了这么多帖子,第一次看到这么有深度了!http://5zjg4m.nui.org.cn

2024-07-11 17:31:56

很有品味!http://9cy2.tjshawoluobo.com

2024-07-11 17:44:35

语言表达流畅,没有冗余,读起来很舒服。http://lsq1jr.habjl.com

2024-07-11 17:45:19

灌水不是我的目的!http://zixd.110celulares.com

2024-07-11 18:18:32

楼主的头像是本人吗?http://ha8sl.kytlw.com

2024-07-11 18:30:37

楼主很有经验啊!http://www.2qukuai.com

2024-07-11 18:58:25

楼主看起来很有学问!http://lsxc5.931121.com/2024/5.html

2024-07-11 19:19:16

今天过得很不爽!http://y84.kymiaomu.com

2024-07-11 19:55:39

楼主该去看心理医生了!http://yw96p.fzmnq.com/7/5.html

2024-07-11 20:24:51

被楼主的逻辑打败了!http://l54z2.funonghzs.com/8/4.html

2024-07-11 20:33:36

帖子好乱!http://y44.jhjxgs.com

2024-07-11 20:55:00

楼主该去看心理医生了!http://0aajw4.zoonkin.com

2024-07-11 21:08:20

这么版块的帖子越来越有深度了!http://8yi465.ghwl-tjzx.com

2024-07-11 21:13:47

终于看完了,很不错!http://do3lnb.nui.org.cn

2024-07-11 21:13:54

写的太好啦,评论一个http://7jpjqc.nui.org.cn

2024-07-11 21:16:02

楼主主机很热情啊!http://ust.ghwl-tjzx.com

2024-07-11 21:18:01

收藏了,以后可能会用到!http://y2g7.bljzq.com

2024-07-11 21:24:56

有钱、有房、有车,人人都想!http://8zr0go.syareher.com

2024-07-11 21:26:30

每次看到楼主的帖子都有惊吓!http://lxx30.znboke.com/x/3.html

2024-07-11 21:46:08

楼主的头像能辟邪啊!http://y6hla.446115.com/b/4.html

2024-07-11 21:46:40

东方不败还是灭绝师太啊?http://j0u.nui.org.cn

2024-07-11 21:48:57

看了这么多帖子,第一次看到这么有深度了!http://u9n.nui.org.cn

2024-07-11 22:02:07

这个帖子会火的,鉴定完毕!http://1x1.zoonkin.com

2024-07-11 22:35:45

终于看完了,很不错!http://tlb5.habjl.com

2024-07-11 22:49:52

回帖也有有水平的!http://thnrau.habjl.com

2024-07-11 22:57:20

楼主的帖子提神醒脑啊!http://www.gxmlm.com

2024-07-11 23:12:28

莆田鞋https://ccc444.com

2024-07-11 23:22:14

缺乏激情了!http://mh8oi.shqmcg.com

2024-07-11 23:28:54

安福相册精准查找https://ccc444.com

2024-07-11 23:29:00

今天上网不回帖,回帖就回精华帖!http://ovxrv.pingbanzhamen.com/33/5.html

2024-07-12 00:05:39

好帖子!http://oazj.sczlcn.com

2024-07-12 00:07:21

网站做得不错http://rxo3zm.sczlcn.com

2024-07-12 00:52:25

太邪乎了吧?http://jy9vs.ojy022.cn

2024-07-12 00:54:42

楼主主机很热情啊!http://slerh.sczlcn.com

2024-07-12 01:01:22

楼主很有经验啊!http://i85j.agriculture4.com

2024-07-12 01:09:40

态度决定一切,不错!http://u5ec.bljzq.com

2024-07-12 01:20:04

好无聊啊!http://o73.ly280.com

2024-07-12 01:33:55

很经典,收藏了!http://2d0d.ojy022.cn

2024-07-12 01:44:14

这个帖子好无聊啊!http://tduwuz.wzyuqi.com

2024-07-12 01:45:04

楼主好聪明啊!http://fxm.wzyuqi.com

2024-07-12 02:09:54

帖子很有深度!http://yxc.longkangys.com.cn

2024-07-12 02:13:18

今天的心情很不错啊http://83s.energizeworld.cn

2024-07-12 02:13:58

楼主的帖子提神醒脑啊!http://781.energizeworld.cn

2024-07-12 02:15:06

支持一下,下面的保持队形!http://es7ri.grodaddie.com/5/3.html

2024-07-12 02:33:36

今天的心情很不错啊http://1rxo2.gongjuyou.com

2024-07-12 02:49:42

楼上的这是啥态度呢?http://4bh4g.longkangys.com.cn

2024-07-12 03:04:38

学习雷锋,好好回帖!http://1wb9.energizeworld.cn

2024-07-12 03:12:33

雷锋做好事不留名,都写在帖子里!http://7udcw.qw1m.com

2024-07-12 03:32:35

有钱、有房、有车,人人都想!http://7jn6m.zhijianly.com

2024-07-12 03:36:38

论坛的帖子越来越有深度了!http://871ba2.szxlzxw.cn

2024-07-12 03:49:58

论坛人气好旺!http://t6v7d.ningbotour.com