說到離散化，可能很多人不知道這是什么，小編簡單給大家介紹一下，后面會(huì)詳細(xì)說明，離散化是程序設(shè)計(jì)中一個(gè)常用的技巧，它可以有效的降低時(shí)間復(fù)雜度。其基本思想就是在眾多可能的情況中，只考慮需要用的值。離散化可以改進(jìn)一個(gè)低效的算法，甚至實(shí)現(xiàn)根本不可能實(shí)現(xiàn)的算法。要掌握這個(gè)思想，必須從大量的題目中理解此方法的特點(diǎn)。例如，在建造線段樹空間不夠的情況下，可以考慮離散化。

離散化，把無限空間中有限的個(gè)體映射到有限的空間中去，以此提高算法的時(shí)空效率。

通俗的說，離散化是在不改變數(shù)據(jù)相對(duì)大小的條件下，對(duì)數(shù)據(jù)進(jìn)行相應(yīng)的縮小。

一、什么是離散化？

離散化（Discretization），把無限空間中有限的個(gè)體映射到有限的空間中去，以此提高算法的時(shí)空效率。通俗的說，離散化是在不改變數(shù)據(jù)相對(duì)大小的條件下，對(duì)數(shù)據(jù)進(jìn)行相應(yīng)的縮小。例如：

原數(shù)據(jù)：1, 999, 100000, 15；處理后：1,3,4,2。

原數(shù)據(jù)：{100, 200}，{20, 50000}，{1, 400}；處理后：{3,4}，{2,6}，{1,5}。

有的時(shí)候，我們會(huì)發(fā)現(xiàn)對(duì)于一個(gè)序列，它的值域很大，對(duì)應(yīng)算法的復(fù)雜度是 Θ(值域) 的。離散化是程序設(shè)計(jì)中一個(gè)常用的技巧，它可以有效的降低時(shí)間復(fù)雜度。其基本思想就是在眾多可能的情況中，只考慮需要用的值。離散化可以改進(jìn)一個(gè)低效的算法，甚至實(shí)現(xiàn)根本不可能實(shí)現(xiàn)的算法。例如，在建造線段樹空間不夠的情況下，可以考慮離散化。

離散化的原理和實(shí)現(xiàn)都很簡單。為了確保不出錯(cuò)且盡可能地提高效率，我們希望離散化能實(shí)現(xiàn)以下幾種功能：

1. 保證離散化后的數(shù)據(jù)非負(fù)且盡可能的小

2. 離散化后各數(shù)據(jù)項(xiàng)之間的大小關(guān)系不變，原本相等的也要保持相等。

由此，找出數(shù)據(jù)項(xiàng)在原序列中從小到大排第幾就是離散化的關(guān)鍵?？梢酝ㄟ^下面的方法以 O(n logn) 的時(shí)間復(fù)雜度完成離散化，n 為序列長度。

二、離散化兩種方法

離散化一共有兩種方法，方法一重復(fù)元素離散化后的數(shù)字相同，方法二重復(fù)元素離散化后的數(shù)字不相同。用的最多的是方法一。

（一）方法一：重復(fù)元素離散化后的數(shù)字相同

例如：對(duì)于序列 [105，35，35，79，-7]，排序并去重后變?yōu)?[-7，35，79，105]，由此就得到了對(duì)應(yīng)關(guān)系 -7->1, 35->2, 79->3, 105->4。

基本的步驟可以分為：

1. 用一個(gè)輔助的數(shù)組把你要離散的所有數(shù)據(jù)存下來。

2. 排序，排序是為了后面的二分。

3. 去重，因?yàn)槲覀円ＷC相同的元素離散化后數(shù)字相同。

4. 索引，再用二分把離散化后的數(shù)字放回原數(shù)組。

對(duì)應(yīng)的代碼如下：

#include<algorithm> // 頭文件 
 
const int MAXN = 1e6+4;
//n 原數(shù)組大小 num 原數(shù)組中的元素 lsh 離散化的數(shù)組 cnt 離散化后的數(shù)組大小 
int lsh[MAXN], cnt, num[MAXN], n;
 
for (int i=1; i<=n; i++) {
    scanf("%d",&num[i]);
    lsh[i] = num[i];	
}
 
sort(lsh+1 , lsh+n+1);//排序
cnt = unique(lsh+1, lsh+n+1) - lsh - 1;//去重
 
//二分查找
for(int i=1; i<=n; i++) {
    num[i] = lower_bound(lsh+1 , lsh+cnt+1 , num[i]) - lsh;
}

在這段代碼中，num[] 經(jīng)過離散，范圍就變成了 m。

數(shù)據(jù)解析

比如，這組數(shù)據(jù)：

1,23424,242,65466,242,0

排序后得到：

0,1,242,242,23424,65466

然后會(huì)去重，得到：

0,1,242,23424,65466

然后離散化的到：

1,3,2,4,2,0

注意事項(xiàng)：

（1）去重并不是把數(shù)組中的元素刪去，而是重復(fù)的部分元素在數(shù)組末尾，去重之后數(shù)組的大小要減一。

（2）二分的時(shí)候，注意二分的區(qū)間范圍，一定是離散化后的區(qū)間。

（3）如果需要多個(gè)數(shù)組同時(shí)離散化，那就把這些數(shù)組中的數(shù)都用數(shù)組存下來。

（二）方法二：重復(fù)元素離散化后的數(shù)字不相同

例如：對(duì)于序列 [105，35，35，79，-7]，排序后變?yōu)?[-7，35，35，79，105]，由此就得到了對(duì)應(yīng)關(guān)系 -7->1，35->2，35->3，79->4，105->5。

基本的步驟可以分為：

1. 用一個(gè)輔助的數(shù)組把你要離散的所有數(shù)據(jù)存下來。

2. 排序。

3. 枚舉著放回原數(shù)組。

對(duì)應(yīng)的代碼如下：

#include<algorithm>
 
struct Node {
    int data , id;
    bool operator < (const Node &a) const {
	return data < a.data;
    }
};
 
const int MAXN = 1e5+4;
Node num[MAXN];//原數(shù)組
int rank[MAXN];//離散化后數(shù)組
int n;
 
for (int i=1; i<=n; i++) {
    scanf("%d",&num[i].data);
    num[i].id = i;
}
 
sort(num+1 , num+n+1);
 
for (int i=1; i<=n; i++) {
    rank[num[i].id] = i;
}

這種方法復(fù)雜度比上面那一種要優(yōu)，但不能處理重復(fù)元素。它直接用結(jié)構(gòu)體存儲(chǔ)原本的數(shù)列的元素的位置，然后排序以后將他們?cè)僦匦沦x值。那么 rank[] 就是結(jié)構(gòu)體 num[] 離散化后的結(jié)果。

數(shù)據(jù)解析

原始數(shù)據(jù)：

data: 3 6 5 10 8
id : 1 2 3 4 5

排序以后：

data: 3 5 6 8 10
id: 1 3 2 5 4

離散化以后：

data: 3 5 6 8 10
id: 1 3 2 5 4
rank: 1 2 3 4 5

再按原來的順序排列：

data: 3 6 5 10 8
rank: 1 3 2 5 4