• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

什么是离散化?C++实现方法

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

简介

离散化本质上可以看成是一种 哈希 ,其保证数据在哈希以后仍然保持原来的全/偏序关系。

通俗地讲,就是当我们只关心数据的大小关系时,用排名代替原数据进行处理的一种预处理方法。离散化本质上是一种哈希,它在保持原序列大小关系的前提下把其映射成正整数。当原数据很大或含有负数、小数时,难以表示为数组下标,一些算法和数据结构(如BIT)无法运作,这时我们就可以考虑将其离散化。

用来离散化的可以是大整数、浮点数、字符串……等等。

实现

C++ 离散化有现成的 STL 算法:

离散化数组

将一个数组离散化,并进行查询是比较常用的应用场景:

// a[i] 为初始数组,下标范围为 [1, n]
// len 为离散化后数组的有效长度
std::sort(a + 1, a + 1 + n);
len = std::unique(a + 1, a + n + 1) - a -
      1;  // 离散化整个数组的同时求出离散化后本质不同数的个数。

在完成上述离散化之后可以使用 std::lower_bound 函数查找离散化之后的排名(即新编号):

std::lower_bound(a + 1, a + len + 1, x) - a;  // 查询 x 离散化后对应的编号

同样地,我们也可以对 vector 进行离散化:

// std::vector<int> a, b; // b 是 a 的一个副本
std::sort(a.begin(), a.end());
a.erase(std::unique(a.begin(), a.end()), a.end());
for (int i = 0; i < n; ++i)
  b[i] = std::lower_bound(a.begin(), a.end(), b[i]) - a.begin();

实际演示:

现在我们有序列 A=[10, 23, 35, 3, -40, 3] 。我们先复制一个同样的序列:

int C[N];
memcpy(C, A, sizeof(A));

排序,去重:

sort(C, C + n);
int l = unique(C, C + n) - C; // l为不重复元素的数量

std::unique()的返回值是一个迭代器(对于数组来说就是指针了),它表示去重后容器中不重复序列的最后一个元素的下一个元素。所以可以这样作差求得不重复元素的数量。现在我们有C=[-40, 3, 10, 23, 35]。

再用一个数组,储存A中每个元素在C中的排名:

int L[MAXN];
for (int i = 0; i < n; ++i)
    L[i] = lower_bound(C, C + l, A[i]) - C + 1; // 二分查找

这样我们就实现了原序列的离散化。得到 L=[3, 4, 5, 2, 1, 2]

因为排序和n次二分查找的复杂度都是 \(\mathcal{O}(n\ log\ n)\) ,所以离散化的复杂度也是 \(\mathcal{O}(n\ log\ n)\) 。完整代码很短:

int C[N], L[N];
// 在main函数中...
memcpy(C, A, sizeof(A)); // 复制
sort(C, C + n); // 排序
int l = unique(C, C + n) - C; // 去重
for (int i = 0; i < n; ++i)
    L[i] = lower_bound(C, C + l, A[i]) - C + 1; // 查找

离散化也不一定要从小到大排序,有时候也需要从大到小。这时在排序和查找时相应地加上greater<int>()就可以了。


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Cookie]C#CookieHelper--C#操作Cookie的帮助类(转载)发布时间:2022-07-13
下一篇:
C++内联汇编方式发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap