离散化 笔记与思路整理

之前写到树状数组求逆序对的时候提到了大数据需要离散化的处理。今天整理一下离散化的方法。

首先，离散化用于处理的数据具有以下特点：

1、很大或有负数，但数据量不是很大；

2、只需要大小关系，而具体数值没有意义。

因此，用离散化处理后的数据大小关系不变，但是更利于计算，尤其是类似于桶排序的需要将数据变为数组下标的操作。例如，数组 {122136, 0, -12, 1, 4} 离散化后为 {5, 2, 1, 3, 4} 。

一、利用STL

1、对原序列进行排序；

2、去掉重复的元素，以保证相同元素离散化后结果相同；

3、原数组中的每个数现在在数组中的位置即为离散化后的值。

代码实现：

//a[]为原数组，t[]为临时数组，n为元素个数 
void dsc(){
    memcpy(t, a, n * sizeof(int)); //复制数组到临时数组
    sort(t, t+n); //升序排序
    int len = unique(t, t+n) - t - 1; //去重，len为去重后数组长度
    for(int i=0; i<n; i++){
        a[i] = lower_bound(t, t+len, a[i]) - t; //找到a[i]位置
    }
}

二、结构体存储

1、使用结构体储存每个元素的值与位置；

2、以值为关键字排序；

3、循环赋值，遇到相邻相同值不变即可；

4、如果需要，以位置为关键字排序恢复原位置。

代码实现：

struct node{
    int val, pos;
} a[maxn]; //存储值与位置
bool cmp(const node &a, const node &b){
    return a.val < b.val;
} //以值为关键字排序
void dsc(){
    sort(a, a+n, cmp);
    int curr = 0, cnt = -1; //-1是为了使第一项为0
    while(curr < n){
        if(a[curr+1].val == a[curr].val) cnt --; //相同值元素离散化后也相同
        a[curr].val = ++ cnt;
        curr ++;
    }
    //sort(a, a+n, cmp_based_on_position); //恢复顺序
}