之前我的離散化方法一直用set和map做，感覺使用stl不夠優越。剛剛發現線段樹PPT給了一種離散化的新姿勢。。。

ax數組：要進行離散化的數組

bx數組：離散化后的數組

id數組：ax數組的rank數組。即排序后id[i]表示為ax數組中第i大的數的位置。?

如果要從原數->離散化后的數，還是需要用map，但是bx數組已經與ax數組形成了對應關系，所以map完全可以避免。

#include<bits/stdc++.h> #define eps 1e-9 #define FOR(i,j,k) for(int i=j;i<=k;i++) #define MAXN 1005 #define MAXM 40005 #define INF 0x3fffffff #define PB push_back #define MP make_pair #define X first #define Y second #define lc (k<<1) #define rc ((k<<1)1) using namespace std; typedef long long LL; int i,j,k,n,m,x,y,T,ans,big,cas,num,len; bool flag;int ax[MAXN],bx[MAXN],mp[MAXN],id[MAXN]; bool cmp(const int &x,const int &y) {return ax[x]<ax[y]; }void discreatize(int n) {for (int i=0;i<n;i++) id[i]=i;sort(id,id+n,cmp);//排序后id[i]表示為ax數組中第i大的數的位置。 mp[1]=ax[id[0]];//對應關系 bx[id[0]]=1;//bx數組為ax離散化后的數組。 for (int i=1,k=1;i<n;i++){if (ax[id[i]]==ax[id[i-1]]) bx[id[i]]=k;else mp[++k]=ax[id[i]],bx[id[i]]=k;} } int main() {scanf("%d",&n);for (i=0;i<n;i++) scanf("%d",&ax[i]);discreatize(n);printf("id:\n");for (i=0;i<n;i++) printf("%d ",id[i]);printf("\nbx:\n");for (i=0;i<n;i++) printf("%d ",bx[i]);printf("\n");return 0; }

?

轉載于:https://www.cnblogs.com/zhyfzy/p/4420441.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

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

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