离散化是程序设计中一个常用的技巧，它可以有效的降低时间和空间复杂度。

离散化，就是把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。
打个比方：现在有一组很大的数据

1,23424,21472313246768,6594,95,0,65535313

如果将这些数作为数组的下标来保存对应的属性时，我们将需要开一个很大的数组。以上方数据为例，这个数组至少要开21472313246768这么大的空间，这样很多题目的空间限制这关都过不了了，怎么办呢？当数据只需表示出它们之间的相对大小关系，而不需表示出具体数值时，我们就要用一个小技巧——离散化。
还是以上面的数据为例，经过离散化处理后，数据就成了：

1,4,6,3,2,0,5

神不神奇，意不意外！！！

——不意外！！！

在这里，我就献上处理数据的程序，教大家如何实现。
第一种方法：

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++自带的一个函数，表示对一个数列去重，然后返回不重复的元素个数，当然在后面要减去首地址。那么这种离散化对于有重复元素的数列也可以适用，但复杂度相对后面要讲的第二种方法会高些。
比如，这组数据：

1,23424,242,65466,242,0

进入这段代码后，首先会排个序得到：

0,1,242,242,23424,65466

然后会去重，得到：

0,1,242,23424,65466

然后离散化的到：

1,3,2,4,2,0

第二种方法：

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

今天的讲解就到了这里，相信大家对离散化有一定的了解了。来，做个题目练练手吧：
P1056图形面积-vijos
P1667 数列-洛谷

来自简书
发表于：2019-2-9
已同步至：

• 简书
• 头条号（今日头条）
• 新浪微博

参考文献：
离散化_百度百科
离散化 - HolseLee - 博客园

C Studio工作室出品

作者微博