資料離散化

一、概述

資料離散化是一個非常重要的思想。

為什麼要離散化?當以權值為下标的時候，有時候值太大，存不下。 是以把要離散化的每一個數組裡面的數映射到另一個值小一點的數組裡面去。

打個比方，某個題目告訴你有10^4個數，每個數大小不超過10^10，要你對這些數進行操作，那麼肯定不能直接開10^10大小的數組，但是10^4的範圍就完全沒問題。

我們來看一下定義：離散化，把無限空間中有限的個體映射到有限的空間中去，以此提高算法的時空效率。（by百度百科）

通俗的說，離散化是在不改變資料相對大小的條件下，對資料進行相應的縮小。例如：

原資料：1,999,100000,15；處理後：1,3,4,2；

原資料：{100,200}，{20,50000}，{1,400}；

處理後：{3,4}，{2,6}，{1,5}；

但是離散化僅适用于隻關注元素之間的大小關系而不關注元素本身的值!

二、原理與操作

假如你隻想簡單操作一下，如求個逆序對什麼的，那直接排序後将它的順序覆寫回去就可以啦。（它不能去重）

假如你想寫的更加專業就要采用以下步驟：

1、排序

2、去重

3、索引

首先我們要對所要進行離散化的資料進行排序：一般使用sort對數組或結構體排序。

然後是去重操作，為了寫出高效的代碼，我們需要複習兩個STL函數：unique（）和lower_bound（），他們同時隸屬于#include<algorithm>。

unique的作用是“去掉”容器中相鄰元素的重複元素（不一定要求數組有序），它會把重複的元素添加到容器末尾（是以數組大小并沒有改變），而傳回值是去重之後的尾位址；

函數lower_bound()在first和last中的前閉後開區間進行二分查找，傳回大于或等于val的第一個元素位置。如果所有元素都小于val，則傳回last的位置。【ps.upper_bound是傳回第一個大于b[x]的指針，upper_bound（）=lower_bound（）+1】

關鍵代碼如下：

int lsh[1000], lshcopy[1000], sy[1000]; 
int size=unique(sy,sy+n)-sy;
lsh[i]=lower_bound(sy,sy+size,lshcopy[i])-sy;      

測試代碼如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int lsh[1000], lshcopy[1000], sy[1000]; //lsh[n]是即将被離散化的數組，lshcopy[n]是a[n]的副本，sy[n]用于排序去重後提供離散化後的值
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&sy[i]);
        lshcopy[i]=sy[i];
            
    } 
    sort(sy,sy+n);//第一步排序 
    for(int i=0;i<n;i++)
    {
        cout<<'('<<sy[i]<<')';
        cout<<"\n";
    }
    int size=unique(sy,sy+n)-sy;//unique顯示去重後的個數 
    printf("size is : %d",size);
    printf("\n");
    for(int i=0;i<n;i++)
    {
        lsh[i]=lower_bound(sy,sy+size,lshcopy[i])-sy; //即lsh[i]為lshcopy[i]離散化後對應的值  
        printf("lsh is : %d",lsh[i]);    
    }
 
}      

友善了解，貼張圖吧：

三、簡單版

假如上面的你看的雲裡霧裡，我決定更新一個簡單版。

struct Node{
int val, order;
}node[maxn];
 
for(int i=1; i<=n; i++) {
    if(i==1 || node[i].val!= node[i-1].val) { //去重
        r[node[i].order] = i;
    }
}      

 r數組負責收集離散後的結果。