【概述】

離散化是數(shù)據(jù)結(jié)構(gòu)中的一個常用技巧，其可以有效的降低時空復(fù)雜度，其基本思想就是在眾多可能的情況中，只去考慮需要用到的值，通過離散化，可以改進(jìn)低效的算法，甚至實(shí)現(xiàn)根本不可能實(shí)現(xiàn)的算法。

對于一些數(shù)量較少，但數(shù)值較大或者可能出現(xiàn)負(fù)數(shù)這種難以處理的數(shù)據(jù)，自身無法作為數(shù)組的下標(biāo)保存對應(yīng)的屬性，如果這時只是需要這些數(shù)據(jù)的相對屬性， 那么可以對其進(jìn)行重新賦值，即進(jìn)行離散化處理。

簡單來說，對于 n 個數(shù)據(jù)，當(dāng) n 很小而每個數(shù)據(jù) a[i] 的數(shù)據(jù)范圍很大時，就可以考慮離散化為更小的值，將他們重新賦值為 [1,n] 之間的數(shù)據(jù)，從而實(shí)現(xiàn)更多的算法。

例如：有 1E5 個數(shù)，每個數(shù)的大小不超過 1E9，要對這些數(shù)進(jìn)行某些操作（并查集等），那么肯定不能直接開 1E9 大小的數(shù)組，但是 1E5 的范圍就完全沒問題，也就是說，當(dāng)不需要這些數(shù)據(jù)具體是多少時，只需要知道他們的相對大小。

離散化分為兩種，一種是重復(fù)的元素離散化后數(shù)值仍相同，一種則是重復(fù)的元素離散化后數(shù)值不同。

【STL+二分實(shí)現(xiàn)離散化】

使用?STL+二分 實(shí)現(xiàn)離散化，重復(fù)的元素數(shù)值仍相同，其實(shí)質(zhì)就是利用一個輔助數(shù)組將要離散的數(shù)據(jù)保存下來，然后進(jìn)行排序去重，最后再用二分將離散數(shù)據(jù)的位置放回原數(shù)組。

注：

• 去重并不是將數(shù)組中重復(fù)的元素刪除，而是將重復(fù)的元素放在數(shù)組末尾
• 二分時，要注意二分的區(qū)間范圍一定是離散化后的區(qū)間

例如：對于數(shù)組 {6,8,4,9,5,6,7,4}，在排序后得到 {4,4,5,6,6,7,8,9}，去重后得到 {4,5,6,7,8,9}，經(jīng)過二分后，原序列變?yōu)?{3,5,1,6,2,3,4,1}

int temp[N],a[N]; int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];temp[i]=a[i];//輔助數(shù)組臨時存儲}sort(temp+1,temp+n+1);//排序，便于去重int len=unique(temp+1,temp+n+1)-temp-1;//去重，len為去重后數(shù)組長度for(int i=1;i<=n;i++)//a[i]即為離散化后的數(shù)組a[i]=lower_bound(temp+1,temp+len+1,a[i])-temp; }

【用數(shù)組離散】

使用數(shù)組實(shí)現(xiàn)離散化，重復(fù)的元素數(shù)值不同，其直接用結(jié)構(gòu)體存儲原序列元素的位置，經(jīng)過排序后將他們重新賦值，最后將結(jié)果存放在 rank 數(shù)組中。

例如：

對于序列 {3,6,5,10,8}，其初始值和 id 為：?

經(jīng)過排序后：

進(jìn)行離散化：

再按照原來的順序進(jìn)行排列：

此時，rank 數(shù)組就是離散化后的值

struct Node{int val,id;bool operator < (const Node &rhs)const{//按值排序return val<rhs.val;} }a[N]; int rank[N];//離散化后的值 int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i].val;a[i].id=i;//記錄序號}sort(a+1,a+n+1);//按值排序for(int i=1;i<=n;i++)//進(jìn)行映射rank[a[i].id]=i; }

【例題】

• 程序自動分析（洛谷-P1955）(離散化+并查集)：點(diǎn)擊這里
• Making the Grade（POJ-3666）(離散化思想+線性DP)：點(diǎn)擊這里
• Mindis（HDU-6670）(離散化+網(wǎng)格圖建圖+bfs)：點(diǎn)擊這里
• Parity game（POJ-1733）(離散化+帶權(quán)并查集區(qū)間問題)：點(diǎn)擊這里

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的常用技巧 —— 离散化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。