目錄

創(chuàng)新互聯(lián)公司提供成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站、網(wǎng)頁設(shè)計(jì)，品牌網(wǎng)站建設(shè)，1元廣告等致力于企業(yè)網(wǎng)站建設(shè)與公司網(wǎng)站制作，10年的網(wǎng)站開發(fā)和建站經(jīng)驗(yàn),助力企業(yè)信息化建設(shè)，成功案例突破數(shù)千家,是您實(shí)現(xiàn)網(wǎng)站建設(shè)的好選擇.

算法原理

算法模板

1）手工編碼

2）c++用STL函數(shù)實(shí)現(xiàn)離散化

附錄：

---

算法原理

? 給出一列數(shù)字，在有些情況下，這些數(shù)字的值得絕對(duì)大小不重要，而相對(duì)大小很重要。例如，對(duì)一個(gè)班級(jí)學(xué)生的成績進(jìn)行排名，此時(shí)不關(guān)心成績的絕對(duì)值，只需要輸出排名，如分?jǐn)?shù)為{95，50，72，21}，排名為{1，3，2，4}。

? 離散化就是用數(shù)字得相對(duì)值替代他們得絕對(duì)值。離散化是一種數(shù)據(jù)處理的技巧。

它把分布廣而稀疏的數(shù)據(jù)轉(zhuǎn)換為密集分布,從而能夠讓算法更快速、更省空間地處理。

例如，（4000,201,11,45,830),數(shù)字的分布很稀疏,按大小排序?yàn)?5,3,1,2,4),若算法處理的是數(shù)字的相對(duì)位置問題,那么對(duì)后者的處理更容易。

離散化步驟如下。

1）排序：首先需要對(duì)數(shù)列排序,排序后才能確定相對(duì)大小。

2）離散化：把排序后的數(shù)列元素從 1開始逐個(gè)分配數(shù)值,完成離散化。

3）歸位：把離散化后的每個(gè)元素放回原始位置,結(jié)束。圖 2.15 演示了把(4000,201,11,45,830)離散化為(5,3,1,2,4)的過程。帶下畫線的字記錄了原始位置,相當(dāng)于數(shù)據(jù)的原始地址,最后的歸位需要利用這些下畫線數(shù)字。

?????

算法模板 1）手工編碼

給定得數(shù)列中經(jīng)常有重復(fù)的數(shù)據(jù)，如{4000，201，11，45，11}.數(shù)字11重復(fù)了，可以分為兩種情況進(jìn)行離散化

1）一般把相同的數(shù)據(jù)離散化為相同的數(shù)據(jù)，即把{4000，201，11，45，11}.離散化為{5，4，1，3，1}.

下面是代碼，其中olda[]記錄原始數(shù)據(jù)，newa[]是離散化的結(jié)果。

#include#define N  500010   //自己定義一個(gè)范圍
struct node{
  int val;              //元素的值
  int id;               //元素的位置
}olda[N]; //離散化之前的原始數(shù)據(jù)

int newa[N]; //離散化后的結(jié)果

int cmp(const void *a,const void *b)
	{ 
	 struct node *aa = (struct node *)a;
     struct node *bb = (struct node *)b;
     return (((aa->val) >(bb->val)));	
	}
	
int main(){
 	int n;      
	scanf("%d",&n);                  //讀元素個(gè)數(shù)
    for(int i=1;i<=n;i++)
	{
        scanf("%d",&olda[i].val);                //讀元素的值
        olda[i].id = i;                          //記錄元素的位置
	}
	qsort(&olda[1],n,sizeof(olda[1]),cmp);             //對(duì)元素的值排序
    for(int i=1;i<=n;i++)
	{                       //生成 newa[]
		newa[olda[i].id]=i; //這個(gè)元素原來的位置在olda[i].id，把它的值賦為i，i是離散化后的新值
	    if(olda[i].val == olda[i-1].val)          //若兩個(gè)元素的原值相同，把新值賦為相同
			newa[olda[i].id] = newa[olda[i-1].id];
    }
    for(int i=1;i<=n;i++)  
	printf("%d ",newa[i]); //打印出來看看
    return 0;
}

2）有時(shí)要求后出現(xiàn)的數(shù)據(jù)比先出現(xiàn)的大，即把{4000，201，11，45，11}.離散化為{5，4，1，3，2}.把上面的代碼的倒數(shù)第六七行注釋即可。

對(duì)于c++玩家，若需要對(duì)重復(fù)的數(shù)據(jù)進(jìn)行去重，可以使用unique函數(shù)

2）c++用STL函數(shù)實(shí)現(xiàn)離散化

可以用 STL的 lower bound()和unique函數(shù)實(shí)現(xiàn)離散化。
lower_bound()函數(shù)的功能是在有序的數(shù)列中查找某個(gè)元素的相對(duì)位置。這個(gè)位置正好是做離散化時(shí)元素初值對(duì)應(yīng)的新值。
有時(shí)還需要用 unique()函數(shù)去重,下面分別討論不去重和去重情況下的操作。
(1)不去重,把相同的數(shù)據(jù)離散化為相同的數(shù)據(jù)。把(4000,201,11,45,11)離散化為(5,4,1,3,1),代碼如下。

#includeusing namespace std;
const int N = 500010;  // 自己定義一個(gè)范圍
int olda[N];           // 離散化前
int newa[N];           // 離散化后
int main(){
    int n;    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&olda[i]);      //讀元素的值
        newa[i] = olda[i];
	}
    sort(olda+1,olda+1+n);         //排序
    int cnt = n;
  //cnt = unique(olda+1,olda+1+n)-(olda+1);  //去重，cnt是去重后的數(shù)量
    for(int i=1;i<=cnt;i++)                  //生成 newa[]
		newa[i]=lower_bound(olda+1,olda+1+n,newa[i])-olda; 
                   //查找相等的元素的位置，這個(gè)位置就是離散化后的新值
    for(int i=1;i<=cnt;i++)   printf("%d ",newa[i]);   //打印出來看看        
    printf("\n cnt=%d",cnt);    
    return 0;
}

2）去重，把相同的數(shù)據(jù)離散化為一個(gè)數(shù)據(jù)，上述代碼加上第14行的去重功能后，離散化為{4，3，1，2}

附錄：

?

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前標(biāo)題：離散化算法-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://weahome.cn/article/djdopd.html