引入

離散化，就是把一些很離散的點給重新分配。

舉個例子，如果一個坐標軸很長(>1e10)，給你1e4個坐標，詢問某一個點，坐標比它小的點有多少。

很容易就知道，對于1e4個點，我們不必把他們在坐標軸上的位置都表示出來，因為我們比較有多少比它小的話，只需要知道他們之間的相對大小就可以，而不是絕對大小，這，就需要離散化。

而離散化又分為兩種，分為的兩種是對于重復元素來劃分的。第一種是重復元素離散化后的數字相同，第二種就是不同。

第一種

其實就是用一個輔助的數組把你要離散的所有數據存下來。

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

去重，因為我們要保證相同的元素離散化后數字相同。

再用二分把離散化后的數字放回原數組。

代碼如下。

#include<algorithm> // 頭文件 //n 原數組大小 num 原數組中的元素 lsh 離散化的數組 cnt 離散化后的數組大小 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;

注意事項：

1.去重并不是把數組中的元素刪去，而是重復的部分元素在數組末尾，去重之后數組的大小要減一

2.二分的時候，注意二分的區間范圍，一定是離散化后的區間

3.如果需要多個數組同時離散化，那就把這些數組中的數都用數組存下來

第二種

第二種方式其實就是排序之后，枚舉著放回原數組

用一個結構體存下原數和位置，按照原數排序

我結構體里面寫了個重載，也可以寫一個比較函數

最后離散化后數在rank[]rank[]里面

#include<algorithm> struct Node {int data , id;bool operator < (const Node &a) const {return data < a.data;} }; Node num[MAXN]; int rank[MAXN] , 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;

總結

先送一道有離散化的題：Luogu1955

很水的一道題，解析在這：NOI2015程序自動分析

用的最多的是第一種方法，第二種方法感覺比較陌生，不過還是需要學的。（20190506第二種方法On啊，，第一種是nlogn的，但是第二種方法只適用于無重復元素的。對于第一種方法，當所有a[i]<2e6這樣子時，可以開數組預處理一下每個數的位置，也可以優化到nlogn預處理之后單次查詢O1，有的同學說，那你a[i]<2e6了，直接開數組不就行了嗎還要啥離散化，但是你別忘了，你萬一是個二維數組呢？怎么開？比如這個題【CodeForces - 255C】）。

轉自https://blog.csdn.net/weixin_43061009/article/details/82083983

總結

以上是生活随笔為你收集整理的算法笔记 -- 离散化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。