邢台网站建设网站,电商erp软件,做业务网站,广告媒体资源平台离散化
离散化#xff1a;不关注数字本身#xff0c;只关注大小关系时#xff0c;利用排名代替原数据
本质#xff1a;一种哈希#xff0c;将离散的数字、浮点数#xff0c;转换成 1 − n 1-n 1−n
例如#xff1a;【 100 #xff0c; 200 #xff0c; 300 #…离散化
离散化不关注数字本身只关注大小关系时利用排名代替原数据
本质一种哈希将离散的数字、浮点数转换成 1 − n 1-n 1−n
例如【 100 200 300 400 500 100200300400500 100200300400500】离散化后为【 1 2 3 4 5 12345 12345】
所有仅关注偏序关系的题目均可以先离散化
一般不会单独考离散化会结合树状数组、线段树等结构一起考先离散化后数组变成 1 − n 1-n 1−n此时可以当作下标
数组 a a a 的离散化步骤
把 a a a 拷贝一份设置为 b b b对 b b b 排序、去重把 a a a 中每个元素设置为 b b b 数组中的下标二分查找
写法一
from bisect import bisect_left
def Discrete(a)::param a: 输入列表a:return: 返回离散后的结果# 拷贝一份b排序去重b list(set(a))b.sort()ans []# 对a中的每个元素x将x转换成b列表中的下标for x in a:ans.append(bisect_left(b, x))return ans写法二
def Discrete(a)::param a: 输入列表a:return: 返回离散后的结果# 拷贝一份b排序去重b list(set(a))b.sort()ans []value list(range(len(b)))dic dict(zip(b, value))# 对a中的每个元素x将x转换成b列表中的下标for x in a:ans.append(dic[x])return ans详见个人博客内容离散化
