离散化

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

　　以下内容部分思路来自：

　　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; }

1
2
3
4
5
6
7
8
9
10
11
12
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; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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