开发者社区> 优惠券发放> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

c++离散化处理大范围和重复数据

简介:
+关注继续查看

c++离散化处理大范围和重复数据

关于离散化

有些新手可能会问:离散化是什么?离散化就是将无限空间中有限的个体映射到有限的空间里去。

上面的定义肯定会有人看不懂(其实我刚开始学的时候也看不懂)

用我自己的话来说,就是在不改变数据的相对大小的条件下,对数据进行相应的压缩

可能还是有人看不懂,没关系,我们来看一个例子,顺便来讲一下离散化的基本操作:

现有一个数组:1,100,2367,562,364737,19,1974832947,100,562,2367

如果按照正常的方法,该开1974832947的空间,但是经过离散化后,就不需要

那么step 1:排序

用上面的例子来说,就是将上面的数据排序并去重,得到下面这组数据:

1,19,100,100,562,562,2367,2367,364737,1974832947

然后step 2:通过unique去重使大小与下标对应,并得到去重后的长度,得到下面这组数据:

1,19,100,562,2367,364737,1974832947

接着step 3:通过lower_bound算出离散化后的排列,得到下面这组数据:

1,2,3,4,5,6,7

那么这里就很尴尬了,这组数据无法应用于初始数据

所以在开始,我们多定义1个数组,来记录初始情况下的数据,再用step 3与其进行对应。

最终得到答案:1,3,5,4,6,2,7,3,4,5

下面给出模板:

 View Code
原文地址https://www.cnblogs.com/jasonownblog/p/12906712.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【C++要笑着学】内联函数 inline | auto关键字(C++11) | 范围for | 关键字 nullptr(二)
本章将继续讲解C++入门部分的知识,将对内联函数、改版后的auto关键字、范围for,以及指针空值nullptr 等知识点进行讲解。
0 0
【C++要笑着学】内联函数 inline | auto关键字(C++11) | 范围for | 关键字 nullptr(一)
本章将继续讲解C++入门部分的知识,将对内联函数、改版后的auto关键字、范围for,以及指针空值nullptr 等知识点进行讲解。
0 0
C++程序设计——内联函数、auto、范围for循环、nullptr
C++程序设计——内联函数、auto、范围for循环、nullptr
0 0
C+++——基于范围的for循环
如标题字面意思,就是要基于范围,for循环
0 0
【C++】C++入门 --- 命名空间 | 输入输出 | 缺省函数 | 函数重载 | 引用 | 内联函数 | auto关键字 | 基于范围的for循环 | 指针空值
命名空间 | 输入输出 | 缺省函数 | 函数重载 | 引用 | 内联函数 | auto关键字 | 基于范围的for循环 | nullptr
0 0
C++11新标准之范围for语句
C++11新标准之范围for语句
0 0
C/C++中各种类型int、long、double、char表示范围(最大最小值)
来源:http://blog.csdn.net/xuexiacm/article/details/8122267 1 #include 2 #include 3 #include 4 using namespace std; 5 6 int main(...
547 0
C++各种数据类型表示范围
转自:http://www.cnblogs.com/maowang1991/p/3166928.html #include <iostream> #include <string> #include <limits> using namespace std; int main() { cout << "type: \t\t" &lt
780 0
C++11的for循环,以及范围Range类的实现
C++11支持range-based for循环。这是一个很方便的特性,能省挺多代码。以下代码就能很方便的遍历vector中的元素,并打印出来: 1 2 3 4 5 6 7 8 std::vector int_vec; int_vec.
598 0
【C++常用容器】STL基础语法学习&list容器
简要介绍:将数据进行链式存储,list(链表)是一种物理存储单元上的非连续的存储单元,数据元素的逻辑顺序是通过链表中的指针链接实现的。链表是由一系列结点组成;结点由两部分组成,一个是存储数据元素的数据域,一个是存储下一个结点地址的指针域。
0 0
+关注
优惠券发放
阿里云优惠码阿里云推荐券bieryun.com
文章
问答
文章排行榜
最热
最新
相关电子书
更多
继承与功能组合
立即下载
移动与复制
立即下载
C++课程-对象模型
立即下载