文档章节

离散化

o
 osc_z1hvg4cu
发布于 2018/04/24 20:50
字数 693
阅读 0
收藏 0
c++

精选30+云产品,助力企业轻松上云!>>>

  本来应该是很简单的东西,但是之前学长讲的时候也没怎么听,然后现在遇到需要离散化的题目就有点茫然了。看了下网上大佬们的博客,基本理解了,做个记录。

  以下内容部分思路来自:

  https://blog.csdn.net/xiangaccepted/article/details/73276826


  

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

 


 

  离散化有两种方法:

  第一种, 先看一段代码:  

const int N=1e5+7;
int t[N],a[N];
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>a[i],t[i]=a[i];
  sort(t+1,t+n+1);
  m=unique(t+1,t+n+1)-t-1;
  for(int i=1;i<=n;i++)
    a[i]=lower_bound(t+1,t+m+1,a[i])-t;
}

 

  在这段代码中,a[]经过离散,范围就变成了m。解释一下,unique是c++自带的一个函数,表示对一个数列去重,然后返回不重复的元素个数,当然在后面要减去首地址。那么这种离散化对于有重复元素的数列也可以适用,但复杂度相对后面要讲的第二种方法会高些。

  举个栗子

  {6,8,4,9,5,6,7,4},首先排序后得到{4,4,5,6,6,7,8,9},去重{4,5,6,7,8,9},然后原序列就变成了{3,5,1,6,2,3,4,1}。

  

  第二种,复杂度比上面那一种要优,但不能处理重复元素。

  先看代码:

const int N=1e5+7;
struct Node{
  int v,id;
  bool operator < (const Node a)const{
    return v<a.v;}//排序用
}a[N];
int n,rank[N];
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i].v;
    a[i].id=i;}
  sort(a+1,a+n+1);
  for(int i=1;i<=n;i++)
    rank[a[i].id]=i;
}

  这种方法直接用结构体存储原本的数列的元素的位置,然后排序以后将他们再重新赋值。那么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

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
量化投资_连续数据的离散化

1  首先回答:什么是离散数据?什么是连续数据?   统计学中经常会见到离散数据和连续数据或者离散变量或者连续变量,理解这两种数据的背后含义如下:   1) continuous variable or d...

osc_x4nw3ehr
2018/04/01
2
0
系统学习机器学习之特征工程(四)--分箱总结

首先from wiki给出一个标准的连续特征离散化的定义: 在统计和机器学习中,离散化是指将连续属性,特征或变量转换或划分为离散或标称属性/特征/变量/间隔的过程。这在创建概率质量函数时非常...

Eason.wxd
03/31
0
0
数据离散化处理

百度百科(离散化): 离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。 通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。例如: 原...

osc_8cfq8uoa
2019/08/16
0
0
机器学习模型为什么要将特征离散化

  在学习机器学习中,看过挺多案例,看到很多人在处理数据的时候,经常把连续性特征离散化。为此挺好奇,为什么要这么做,什么情况下才要做呢。 一、离散化原因   数据离散化是指将连续的...

osc_t0zmqrod
2018/08/07
1
0
粒子群优化算法(PSO)之基于离散化的特征选择(FS)(一)

欢迎大家关注我们的网站和系列教程:http://www.tensorflownews.com/,学习更多的机器学习、深度学习的知识! 作者:Geppetto 在机器学习中,离散化(Discretization)和特征选择(Feature Sele...

人工智能遇见磐创
03/25
1
0

没有更多内容

加载失败,请刷新页面

加载更多

skywalking实现分布式系统链路追踪

一、背景 随着微服务的越来越流行,我们服务之间的调用关系就显得越来越复杂,我们急需一个APM工具来分析系统中存在的各种性能指标问题以及调用关系。目前主流的APM工具有CAT、Zipkin、Pinpo...

燚-焱
19分钟前
16
0
2020最新的Spring Boot 分布式锁的具体实现(内附代码)

前言 面试总是会被问到有没有用过分布式锁、redis 锁,大部分读者平时很少接触到,所以只能很无奈的回答 “没有”。本文通过 Spring Boot 整合 redisson 来实现分布式锁,并结合 demo 测试结...

北柠Java
25分钟前
8
0
Shiro中获取Cookie

自定义shiro的SessionIdCookie 在使用shiro的时候,曾经有段时间很苦恼,因为我cookie的sessionId经常无故被改,然后抛There is no session with id [xxxx]的异常。我们知道,当请求过来,s...

豫华商
25分钟前
9
0
JPA和Hibernate有什么区别? [关闭] - What's the difference between JPA and Hibernate? [closed]

问题: I understand that JPA 2 is a specification and Hibernate is a tool for ORM. 我知道JPA 2是一个规范,而Hibernate是ORM的工具。 Also, I understand that Hibernate has more fea......

富含淀粉
42分钟前
14
0
Java知识回顾-基础知识(2)

局部变量/成员变量: 成员变量是属于类的 局部变量是属于方法的 都可以被final修饰 java中使用new 创建实例对象 方法返回值的作用: 方法的返回值 是指方法中的一系列操作有返回结果 返回值的作...

心田已荒
47分钟前
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部